Resolving domination in graphs

Robert C. Brigham; Gary Chartrand; Ronald D. Dutton; Ping Zhang

Mathematica Bohemica (2003)

  • Volume: 128, Issue: 1, page 25-36
  • ISSN: 0862-7959

Abstract

top
For an ordered set W = { w 1 , w 2 , ⋯ , w k } 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 ) , ⋯ , 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 γ ( 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 γ r ( G ) . In this paper, we investigate the relationship among these three parameters.

How to cite

top

Brigham, Robert C., et al. "Resolving domination in graphs." Mathematica Bohemica 128.1 (2003): 25-36. <http://eudml.org/doc/249214>.

@article{Brigham2003,
abstract = {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.},
author = {Brigham, Robert C., Chartrand, Gary, Dutton, Ronald D., Zhang, Ping},
journal = {Mathematica Bohemica},
keywords = {resolving dominating set; resolving domination number; resolving dominating set; resolving domination number},
language = {eng},
number = {1},
pages = {25-36},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Resolving domination in graphs},
url = {http://eudml.org/doc/249214},
volume = {128},
year = {2003},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 128
IS - 1
SP - 25
EP - 36
AB - 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.
LA - eng
KW - resolving dominating set; resolving domination number; resolving dominating set; resolving domination number
UR - http://eudml.org/doc/249214
ER -

References

top
  1. 10.1016/S0166-218X(00)00198-0, Discrete Appl. Math. 105 (2000), 99–113. (2000) MR1780464DOI10.1016/S0166-218X(00)00198-0
  2. Graphs & Digraphs, third edition, Chapman & Hall, New York, 1996. (1996) MR1408678
  3. Resolvability and the upper dimension of graphs, International J. Comput. Math. Appl. 39 (2000), 19–28. (2000) MR1763834
  4. Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998. (1998) MR1605684
  5. On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195. (1976) MR0457289
  6. Leaves of trees, Congr. Numer. 14 (1975), 549–559. (1975) Zbl0316.05102MR0422062
  7. Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445–455. (1988) MR0966610

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.