For an ordered set $W=\{w_1,w_2,...,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the ordered $k$-vector $r\left(v\right|W):=(d(v,w_1),d(v,w_2),...,d(v,w_k))$ is called the metric representation of $v$ with respect to $W$, where $d(x,y)$ is the distance between vertices $x$ and $y$. A set $W$ is called a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. The minimum cardinality of a resolving set for $G$ is its metric dimension. In this paper, we characterize all graphs of order $n$ with metric dimension $n-3$.

A power digraph modulo $n$, denoted by $G(n,k)$, is a directed graph with $Z_n=\{0,1,\cdots ,n-1\}$ as the set of vertices and $E=\{(a,b):a^k\equiv b(modn)\}$ as the edge set, where $n$ and $k$ are any positive integers. In this paper we find necessary and sufficient conditions on $n$ and $k$ such that the digraph $G(n,k)$ has at least one isolated fixed point. We also establish necessary and sufficient conditions on $n$ and $k$ such that the digraph $G(n,k)$ contains exactly two components. The primality of Fermat number is also discussed.

The purpose of this paper is to give characterizations of graphs whose vertex-semientire graphs and edge-semientire graphs have crossing number 2. In addition, we establish necessary and sufficient conditions in terms of forbidden subgraphs for vertex-semientire graphs and edge-semientire graphs to have crossing number 2.

In a graph G, the distance d(u, v) between a pair of vertices u and v is the length of a shortest path joining them. The eccentricity e(u) of a vertex u is the distance to a vertex farthest from u. The minimum eccentricity is called the radius, r(G), of the graph and the maximum eccentricity is called the diameter, d(G), of the graph. The super-radial graph R*(G) based on G has the vertex set as in G and two vertices u and v are adjacent in R*(G) if the distance between them in G is greater than...

Let G = (V(G),E(G)) be a simple graph, and let k be a positive integer. A subset D of V(G) is a k-dominating set if every vertex of V(G) - D is dominated at least k times by D. The k-domination number γₖ(G) is the minimum cardinality of a k-dominating set of G. In [5] Volkmann showed that for every nontrivial tree T, γ₂(T) ≥ γ₁(T)+1 and characterized extremal trees attaining this bound. In this paper we characterize all trees T with γ₂(T) = γ₁(T)+2.

Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum number of...

In this paper we present characterizations of graphs whose plick graphs are planar, outerplanar and minimally nonouterplanar.

The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented by the...

Let G ☐ H denote the Cartesian product of the graphs G and H. In 2004, Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24(3) (2004), 389-402] characterized prism fixers, i.e., graphs G for which γ(G ☐ K₂) = γ(G), and noted that γ(G ☐ Kₙ) ≥ min{|V(G)|, γ(G)+n-2}. We call a graph G a consistent fixer if γ(G ☐ Kₙ) = γ(G)+n-2 for each n such that 2 ≤ n < |V(G)|- γ(G)+2, and characterize this class of graphs. Also in 2004, Burger,...

Let $G$ be a finite group and construct a graph $\Delta \left(G\right)$ by taking $G\setminus \left\{1\right\}$ as the vertex set of $\Delta \left(G\right)$ and by drawing an edge between two vertices $x$ and $y$ if $\langle x,y\rangle$ is cyclic. Let $K\left(G\right)$ be the set consisting of the universal vertices of $\Delta \left(G\right)$ along the identity element. For a solvable group $G$, we present a necessary and sufficient condition for $K\left(G\right)$ to be nontrivial. We also develop a connection between $\Delta \left(G\right)$ and $K\left(G\right)$ when $\left|G\right|$ is divisible by two distinct primes and the diameter of $\Delta \left(G\right)$ is 2.