Geodesic
Resolving domination in graphs
Mathematica Bohemica, Tome 128 (2003) no. 1, pp. 25-36

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 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.
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.
DOI : 10.21136/MB.2003.133935
Classification : 05C12, 05C69
Keywords: resolving dominating set; resolving domination number 
Brigham, Robert C.; Chartrand, Gary; Dutton, Ronald D.; Zhang, Ping. Resolving domination in graphs. Mathematica Bohemica, Tome 128 (2003) no. 1, pp. 25-36. doi: 10.21136/MB.2003.133935
@article{10_21136_MB_2003_133935,
     author = {Brigham, Robert C. and Chartrand, Gary and Dutton, Ronald D. and Zhang, Ping},
     title = {Resolving domination in graphs},
     journal = {Mathematica Bohemica},
     pages = {25--36},
     year = {2003},
     volume = {128},
     number = {1},
     doi = {10.21136/MB.2003.133935},
     mrnumber = {1973422},
     zbl = {1010.05048},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.133935/}
}
TY  - JOUR
AU  - Brigham, Robert C.
AU  - Chartrand, Gary
AU  - Dutton, Ronald D.
AU  - Zhang, Ping
TI  - Resolving domination in graphs
JO  - Mathematica Bohemica
PY  - 2003
SP  - 25
EP  - 36
VL  - 128
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.133935/
DO  - 10.21136/MB.2003.133935
LA  - en
ID  - 10_21136_MB_2003_133935
ER  - 
%0 Journal Article
%A Brigham, Robert C.
%A Chartrand, Gary
%A Dutton, Ronald D.
%A Zhang, Ping
%T Resolving domination in graphs
%J Mathematica Bohemica
%D 2003
%P 25-36
%V 128
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2003.133935/
%R 10.21136/MB.2003.133935
%G en
%F 10_21136_MB_2003_133935

[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. | DOI | MR

[2] G. Chartrand, L. Lesniak: Graphs & Digraphs, third edition. Chapman & Hall, New York, 1996. | MR

[3] G. Chartrand, C. Poisson, P. Zhang: Resolvability and the upper dimension of graphs. International J. Comput. Math. Appl. 39 (2000), 19–28. | MR

[4] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs. Marcel Dekker, New York, 1998. | MR

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

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

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

Cité par Sources :