| Title:
|
Resolving domination in graphs (English) |
| Author:
|
Brigham, Robert C. |
| Author:
|
Chartrand, Gary |
| Author:
|
Dutton, Ronald D. |
| Author:
|
Zhang, Ping |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
128 |
| Issue:
|
1 |
| Year:
|
2003 |
| Pages:
|
25-36 |
| 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 with respect to $W$. A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for $G$ is its dimension $\dim G$. A set $S$ of vertices in $G$ is a dominating set for $G$ if every vertex of $G$ that is not in $S$ is adjacent to some vertex of $S$. The minimum cardinality of a dominating set is the domination number $\gamma (G)$. A set of vertices of a graph $G$ that is both resolving and dominating is a resolving dominating set. The minimum cardinality of a resolving dominating set is called the resolving domination number $\gamma _r(G)$. In this paper, we investigate the relationship among these three parameters. (English) |
| Keyword:
|
resolving dominating set |
| Keyword:
|
resolving domination number |
| MSC:
|
05C12 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 1010.05048 |
| idMR:
|
MR1973422 |
| DOI:
|
10.21136/MB.2003.133935 |
| . |
| Date available:
|
2009-09-24T22:06:36Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/133935 |
| . |
| Reference:
|
[1] G. Chartrand, L. Eroh, M. Johnson, O. R. Oellermann: Resolvability in graphs and the metric dimension of a graph.Discrete Appl. Math. 105 (2000), 99–113. MR 1780464, 10.1016/S0166-218X(00)00198-0 |
| Reference:
|
[2] G. Chartrand, L. Lesniak: Graphs & Digraphs, third edition.Chapman & Hall, New York, 1996. MR 1408678 |
| Reference:
|
[3] G. Chartrand, C. Poisson, P. Zhang: Resolvability and the upper dimension of graphs.International J. Comput. Math. Appl. 39 (2000), 19–28. MR 1763834 |
| Reference:
|
[4] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs.Marcel Dekker, New York, 1998. MR 1605684 |
| Reference:
|
[5] F. Harary, R. A. Melter: On the metric dimension of a graph.Ars Combin. 2 (1976), 191–195. MR 0457289 |
| Reference:
|
[6] P. J. Slater: Leaves of trees.Congr. Numer. 14 (1975), 549–559. Zbl 0316.05102, MR 0422062 |
| Reference:
|
[7] P. J. Slater: Dominating and reference sets in graphs.J. Math. Phys. Sci. 22 (1988), 445–455. MR 0966610 |
| . |
