| Title:
|
The forcing dimension of a graph (English) |
| Author:
|
Chartrand, Gary |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| 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 $. (English) |
| Keyword:
|
resolving set |
| Keyword:
|
basis |
| Keyword:
|
dimension |
| Keyword:
|
forcing dimension |
| MSC:
|
05C12 |
| idZBL:
|
Zbl 0995.05046 |
| idMR:
|
MR1869463 |
| DOI:
|
10.21136/MB.2001.134116 |
| . |
| Date available:
|
2009-09-24T21:56:13Z |
| Last updated:
|
2020-07-29 |
| 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, 10.1006/eujc.1999.0301 |
| Reference:
|
[cz:fgeo] G. Chartrand, P. Zhang: The forcing geodetic number of a graph.Discuss. Math. Graph Theory 19 (1999), 45–58. MR 1704390, 10.7151/dmgt.1084 |
| 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, 10.1002/jgt.3190090403 |
| 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 |
| . |
