For an ordered set W = {w1, w2, . . . , wk} of vertices and a vertex v in a connected graph G, the ordered k-vector r(v|W) := (d(v, w1), d(v, w2), . . . , d(v, wk)) 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.
For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices and a vertex $v$ in a connected graph $G$, the representation of $v$ with respect to $W$ is the $k$-vector $r(v|W)$ = ($d(v, w_1)$, $d(v, w_2),\dots ,d(v, w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is a basis for $G$. The dimension $\dim (G)$ is the number of vertices in a basis for $G$. A resolving set $W$ of $G$ is connected if the subgraph $<W>$ induced by $W$ is a nontrivial connected subgraph of $G$. The minimum cardinality of a connected resolving set in a graph $G$ is its connected resolving number $\mathop {\mathrm cr}(G)$. Thus $1 \le \dim (G) \le \mathop {\mathrm cr}(G) \le n-1$ for every connected graph $G$ of order $n \ge 3$. The connected resolving numbers of some well-known graphs are determined. It is shown that if $G$ is a connected graph of order $n \ge 3$, then $\mathop {\mathrm cr}(G) = n-1$ if and only if $G = K_n$ or $G = K_{1, n-1}$. It is also shown that for positive integers $a$, $b$ with $a \le b$, there exists a connected graph $G$ with $\dim (G) = a$ and $\mathop {\mathrm cr}(G) = b$ if and only if $(a, b) \notin \lbrace
(1, k)\: k = 1\hspace{5.0pt}\text{or}\hspace{5.0pt}k \ge 3\rbrace $. Several other realization results are present. The connected resolving numbers of the Cartesian products $G \times K_2$ for connected graphs $G$ are studied.
Zero forcing number has recently become an interesting graph parameter studied in its own right since its introduction by the ''AIM Minimum Rank–Special Graphs Work Group'', whereas metric dimension is a well-known graph parameter. We investigate the metric dimension and the zero forcing number of some line graphs by first determining the metric dimension and the zero forcing number of the line graphs of wheel graphs and the bouquet of circles. We prove that Z(G) ≤ 2Z(L(G)) for a simple and connected graph G. Further, we show that Z(G) ≤ Z(L(G)) when G is a tree or when G contains a Hamiltonian path and has a certain number of edges. We compare the metric dimension with the zero forcing number of a line graph by demonstrating a couple of inequalities between the two parameters. We end by stating some open problems.
For an ordered set W = {w1, w2,...,wk} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v|W)=(d(v,w1), d(v, w2),...,d(v, wk)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). For a basis W of G, a subset S of W is called a forcing subset of W if W is the unique basis containing S. The forcing number fG(W, dim) of W in G is the minimum cardinality of a forcing subset for W, while the forcing dimension f(G, dim) of G is the smallest forcing number among all bases of G. The forcing dimensions of some well-known graphs are determined. It is shown that for all integers a, b with 0 ≤ a ≤ b and b ≥1, there exists a nontrivial connected graph G with f(G) = a and dim(G) = b if and only if {a, b} ≠ {0, 1}.
For an ordered set W = {w1, w2, . . . , wk} of vertices in a connected graph G and a vertex v of G, the code of v with respect to W is the k-vector cW (v) = (d(v, w1), d(v, w2), . . . , d(v, wk)). The set W is an independent resolving set for G if (1) W is independent in G and (2) distinct vertices have distinct codes with respect to W. The cardinality of a minimum independent resolving set in G is the independent resolving number ir(G). We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs G of order n with ir(G) = 1, n − 1, n − 2, and present several realization results. It is shown that for every pair r, k of integers with k ≥ 2 and 0 ≤ r ≤ k, there exists a connected graph G with ir(G) = k such that exactly r vertices belong to every minimum independent resolving set of G.