## 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\}$$.

### MSC:

 05C12 Distance in graphs

### Keywords:

resolving set; basis; dimension; forcing dimension
Full Text: