The independent resolving number of a graph. (English) Zbl 1050.05043

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

Math. Bohem. 128, No. 4, 379-393 (2003).

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