The forcing dimension of a graph. (English) Zbl 0995.05046

Summary: For an ordered set \(W=\{w_1, w_2, \dots , w_k\}\) 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, w_1),\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. 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 \(f_{G}(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 \leq a \leq b\) and \(b \geq 1\), there exists a nontrivial connected graph \(G\) with \(f(G) = a\) and \(\dim (G) = b\) if and only if \(\{a, b\} \neq \{0, 1\}\).


05C12 Distance in graphs
Full Text: EuDML