MATHEMATICA BOHEMICA, Vol. 128, No. 1, pp. 25-36 (2003)

# Resolving domination in graphs

## Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang

Robert C. Brigham, Department of Mathematics, University of Central Florida, Orlando, FL 32816, USA; Gary Chartrand, Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA; Ronald D. Dutton, Program of Computer Science, University of Central Florida, Orlando, FL 32816, USA; Ping Zhang, Department of Mathematics, Western Michigan University, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu

Abstract: For an ordered set \$W =\{w_1, w_2, \cdots, 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) ,\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 \$\ga(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 \$\ga_r(G)\$. In this paper, we investigate the relationship among these three parameters.

Keywords: resolving dominating set, resolving domination number

Classification (MSC2000): 05C12, 05C69

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]
© 2004–2010 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition