Connected Resolving Sets in Graphs

Abstract

For an ordered set \(W = \{w_1, w_2, \ldots, w_e\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the representation of \(v\) with respect to \(W\) is the \(e\)-vector \(r(v|W) = (d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\), where \(d(x, y)\) represents the distance between the vertices \(x\) and \(y\). The set \(W\) is a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations with respect to \(W\). A resolving set for \(G\) containing a minimum number of vertices is a basis for \(G\). The dimension \(\dim(G)\) is the number of vertices in a basis for \(G\). A resolving set \(W\) of \(G\) is connected if the subgraph \(\langle W \rangle\) induced by \(W\) is a connected subgraph of \(G\). The minimum cardinality of a connected resolving set in a graph \(G\) is its connected resolving number \(cr(G)\). The relationship between bases and minimum connected resolving sets in a graph is studied. A connected resolving set \(W\) of \(G\) is a minimal connected resolving set if no proper subset of \(W\) is a connected resolving set. The maximum cardinality of a minimal connected resolving set is the upper connected resolving number \(cr^+(G)\). The upper connected resolving numbers of some well-known graphs are determined. We present a characterization of nontrivial connected graphs of order \(n\) with upper connected resolving number \(n-1\). It is shown that for a pair \(a,b\) of integers with \(1 \leq a \leq b\) there exists a connected graph \(G\) with \(cr(G) = a\) and \(cr^+(G) = b\) if and only if \((a,b) \neq (1,4)\) for all \(i > 2\).