Article

 Title: The forcing dimension of a graph  (English) Author: Chartrand, Gary Author: Zhang, Ping Language: English Journal: Mathematica Bohemica ISSN: 0862-7959 Volume: 126 Issue: 4 Year: 2001 Pages: 711-720 Summary lang: English . Category: math . Summary: 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 \$. Keyword: resolving set Keyword: basis Keyword: dimension Keyword: forcing dimension MSC: 05C12 idZBL: Zbl 0995.05046 idMR: MR1869463 . Date available: 2009-09-24T21:56:13Z Last updated: 2012-06-18 Stable URL: http://hdl.handle.net/10338.dmlcz/134116 . Reference: [cz:kg] P. Buczkowski, G. Chartrand, C. Poisson, P. Zhang: On \$k\$-dimensional graphs and their bases. Submitted.. Reference: [ce:rg] G. Chartrand, L. Eroh, M. Johnson: Resolvability in graphs and the metric dimension of a graph.(to appear). Reference: [chz:geo] G. Chartrand, F. Harary, P. Zhang: On the geodetic number of a graph.(to appear). MR 1871701 Reference: [cpz:res] G. Chartrand, C. Poisson, P. Zhang: Resolvability and the upper dimension of graphs.(to appear). MR 1763834 Reference: [crz:ddd1] G. Chartrand, M. Raines, P. Zhang: The directed distance dimension of oriented graphs.Math. Bohem. 125 (2000), 155–168. MR 1768804 Reference: [crz:ddd2] G. Chartrand, M. Raines, P. Zhang: On the dimension of oriented graphs.(to appear). MR 1863436 Reference: [cz:dgeo] G. Chartrand, P. Zhang: The geodetic number of an oriented graph.European J. Combin. 21 (2000), 181–189. MR 1742433 Reference: [cz:fgeo] G. Chartrand, P. Zhang: The forcing geodetic number of a graph.Discuss. Math. Graph Theory 19 (1999), 45–58. MR 1704390 Reference: [eh:chr] C. Ellis, F. Harary: The chromatic forcing number of a graph.(to appear). Reference: [h:sur] F. Harary: A survey of forcing parameters in graph theory. Preprint.. Reference: [hm:md] F. Harary, R. A. Melter: On the metric dimension of a graph.Ars Combin. 2 (1976), 191–195. MR 0457289 Reference: [hp:rec] F. Harary, M. Plantholt: The graph reconstruction number.J. Graph Theory 9 (1985), 451–454. MR 0890233 Reference: [pz:ug] C. Poisson, P. Zhang: The dimension of unicyclic graphs. Submitted.(to appear). Reference: [s:lt] P. J. Slater: Leaves of trees.Congress. Numer. 14 (1975), 549–559. Zbl 0316.05102, MR 0422062 Reference: [s:dr] P. J. Slater: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445–455. MR 0966610 .

Files

Files Size Format View
MathBohem_126-2001-4_3.pdf 307.2Kb application/pdf View/Open

Partner of