The forcing dimension of a graph

Chartrand, Gary, and Zhang, Ping. "The forcing dimension of a graph." Mathematica Bohemica 126.4 (2001): 711-720. <http://eudml.org/doc/248877>.

@article{Chartrand2001,
abstract = {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 $.},
author = {Chartrand, Gary, Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {resolving set; basis; dimension; forcing dimension; resolving set; basis; dimension; forcing dimension},
language = {eng},
number = {4},
pages = {711-720},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The forcing dimension of a graph},
url = {http://eudml.org/doc/248877},
volume = {126},
year = {2001},
}

TY - JOUR
AU - Chartrand, Gary
AU - Zhang, Ping
TI - The forcing dimension of a graph
JO - Mathematica Bohemica
PY - 2001
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 126
IS - 4
SP - 711
EP - 720
AB - 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 $.
LA - eng
KW - resolving set; basis; dimension; forcing dimension; resolving set; basis; dimension; forcing dimension
UR - http://eudml.org/doc/248877
ER -