zbMATH — the first resource for mathematics

The independent resolving number of a graph. (English) Zbl 1050.05043
Summary: 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 $$\text{ir} (G)$$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $$G$$ of order $$n$$ with $$\text{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 \geq 2$$ and $$0 \leq r \leq k$$, there exists a connected graph $$G$$ with $$\text{ir} (G) = k$$ such that exactly $$r$$ vertices belong to every minimum independent resolving set of $$G$$.

MSC:
 05C12 Distance in graphs 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Keywords:
distance; resolving set; independent set
Full Text: