G. Chartrand, V. Saenpholphat, P. 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, \dots, w_k\}$ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector
c_W(v) = (d(v, w_1), d(v, w_2), \dots, d(v, w_k) ).
The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\ir(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\ir(G) = 1$, $n-1$, $n-2$, and present several realization results. It is shown that for every pair $r, k$ of integers with $k \geq2$ and $0 \leq r \leq k$, there exists a connected graph $G$ with $\ir(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.
Keywords: distance, resolving set, independent set
Classification (MSC 2000): 05C12, 05C69
Full text available as PDF (smallest), as compressed PostScript (.ps.gz) or as raw PostScript (.ps).
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
