The forcing dimension of a graph

Chartrand, Gary ; Zhang, Ping

Mathematica Bohemica, Tome 126 (2001) no. 4, pp. 711-720.

Résumé

For an ordered set $W=\lbrace w_1, w_2, \cdots , w_k\rbrace $ 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),d(v, w_2),\cdots , 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 \le a \le b$ and $b \ge 1$, there exists a nontrivial connected graph $G$ with $f(G) = a$ and $\dim (G) = b$ if and only if $\lbrace a, b\rbrace \ne \lbrace 0, 1\rbrace $.

Détail

DOI : 10.21136/MB.2001.134116

Classification : 05C12
Keywords: resolving set; basis; dimension; forcing dimension