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\).

05C12 Distance in graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: EuDML