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: