# Article

Full entry | PDF   (0.3 MB)
Keywords:
resolving set; basis; dimension; forcing dimension
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 \$.
References:
[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 1871701
[cpz:res] G. Chartrand, C. Poisson, P. Zhang: Resolvability and the upper dimension of graphs. (to appear). MR 1763834
[crz:ddd1] G. Chartrand, M. Raines, P. Zhang: The directed distance dimension of oriented graphs. Math. Bohem. 125 (2000), 155–168. MR 1768804
[crz:ddd2] G. Chartrand, M. Raines, P. Zhang: On the dimension of oriented graphs. (to appear). MR 1863436
[cz:dgeo] G. Chartrand, P. Zhang: The geodetic number of an oriented graph. European J. Combin. 21 (2000), 181–189. DOI 10.1006/eujc.1999.0301 | MR 1742433
[cz:fgeo] G. Chartrand, P. Zhang: The forcing geodetic number of a graph. Discuss. Math. Graph Theory 19 (1999), 45–58. DOI 10.7151/dmgt.1084 | MR 1704390
[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 0457289
[hp:rec] F. Harary, M. Plantholt: The graph reconstruction number. J. Graph Theory 9 (1985), 451–454. DOI 10.1002/jgt.3190090403 | MR 0890233
[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 0422062 | Zbl 0316.05102
[s:dr] P. J. Slater: Dominating and reference sets in graphs. J. Math. Phys. Sci. 22 (1988), 445–455. MR 0966610

Partner of