# Article

**Keywords:**

distance; resolving set; independent set

**Summary:**

For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ 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 $\mathop {\mathrm ir}(G)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathop {\mathrm 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 \ge 2$ and $0 \le r \le k$, there exists a connected graph $G$ with $\mathop {\mathrm ir}(G) = k$ such that exactly $r$ vertices belong to every minimum independent resolving set of $G$.

References:

[1] F. Buckley, F. Harary:

**Distance in Graphs**. Addison-Wesley, Redwood City, CA, 1990.

MR 1045632
[2] G. Chartrand, L. Lesniak:

**Graphs $\&$ Digraphs, third edition**. CRC Press, Boca Raton, 1996.

MR 1408678
[3] F. Harary, R. A. Melter:

**On the metric dimension of a graph**. Ars Combin. 2 (1976), 191–195.

MR 0457289
[5] P. J. Slater:

**Dominating and reference sets in graphs**. J. Math. Phys. Sci. 22 (1988), 445–455.

MR 0966610