Geodesic
The forcing dimension of a graph
Mathematica Bohemica, Tome 126 (2001) no. 4, pp. 711-720

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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 $.
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 $.
DOI : 10.21136/MB.2001.134116
Classification : 05C12
Keywords: resolving set; basis; dimension; forcing dimension 
Chartrand, Gary; Zhang, Ping. The forcing dimension of a graph. Mathematica Bohemica, Tome 126 (2001) no. 4, pp. 711-720. doi: 10.21136/MB.2001.134116
@article{10_21136_MB_2001_134116,
     author = {Chartrand, Gary and Zhang, Ping},
     title = {The forcing dimension of a graph},
     journal = {Mathematica Bohemica},
     pages = {711--720},
     year = {2001},
     volume = {126},
     number = {4},
     doi = {10.21136/MB.2001.134116},
     mrnumber = {1869463},
     zbl = {0995.05046},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.134116/}
}
TY  - JOUR
AU  - Chartrand, Gary
AU  - Zhang, Ping
TI  - The forcing dimension of a graph
JO  - Mathematica Bohemica
PY  - 2001
SP  - 711
EP  - 720
VL  - 126
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.134116/
DO  - 10.21136/MB.2001.134116
LA  - en
ID  - 10_21136_MB_2001_134116
ER  - 
%0 Journal Article
%A Chartrand, Gary
%A Zhang, Ping
%T The forcing dimension of a graph
%J Mathematica Bohemica
%D 2001
%P 711-720
%V 126
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2001.134116/
%R 10.21136/MB.2001.134116
%G en
%F 10_21136_MB_2001_134116

[cz:kg] P. Buczkowski, G. Chartrand, C. Poisson, P. Zhang: On $k$-dimensional graphs and their bases. Submitted.

[ce:rg] G. Chartrand, L. Eroh, M. Johnson: Resolvability in graphs and the metric dimension of a graph. (to appear).

[chz:geo] G. Chartrand, F. Harary, P. Zhang: On the geodetic number of a graph. (to appear). | MR

[cpz:res] G. Chartrand, C. Poisson, P. Zhang: Resolvability and the upper dimension of graphs. (to appear). | MR

[crz:ddd1] G. Chartrand, M. Raines, P. Zhang: The directed distance dimension of oriented graphs. Math. Bohem. 125 (2000), 155–168. | MR

[crz:ddd2] G. Chartrand, M. Raines, P. Zhang: On the dimension of oriented graphs. (to appear). | MR

[cz:dgeo] G. Chartrand, P. Zhang: The geodetic number of an oriented graph. European J. Combin. 21 (2000), 181–189. | DOI | MR

[cz:fgeo] G. Chartrand, P. Zhang: The forcing geodetic number of a graph. Discuss. Math. Graph Theory 19 (1999), 45–58. | DOI | MR

[eh:chr] C. Ellis, F. Harary: The chromatic forcing number of a graph. (to appear).

[h:sur] F. Harary: A survey of forcing parameters in graph theory. Preprint.

[hm:md] F. Harary, R. A. Melter: On the metric dimension of a graph. Ars Combin. 2 (1976), 191–195. | MR

[hp:rec] F. Harary, M. Plantholt: The graph reconstruction number. J. Graph Theory 9 (1985), 451–454. | DOI | MR

[pz:ug] C. Poisson, P. Zhang: The dimension of unicyclic graphs. Submitted. (to appear).

[s:lt] P. J. Slater: Leaves of trees. Congress. Numer. 14 (1975), 549–559. | MR | Zbl

[s:dr] P. J. Slater: Dominating and reference sets in graphs. J. Math. Phys. Sci. 22 (1988), 445–455. | MR

Cité par Sources :