**
MATHEMATICA BOHEMICA, Vol. 128, No. 4, pp. 379-393 (2003)
**

#
The independent resolving number of a graph

##
G. Chartrand, V. Saenpholphat, P. Zhang

* 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 (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
*