On Resolving Acyclic Partitions of Graphs

Abstract

For a vertex \(v\) of a connected graph \(G\) and a subset \(S\) of \(V(G)\), the distance between \(v\) and \(S\) is \(d(v, S) = \min\{d(v,x) : x \in S\}\), where \(d(v,x)\) is the distance between \(v\) and \(x\). For an ordered \(k\)-partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) of \(V(G)\), the code of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(c_\Pi(v) = (d(v,S_1), d(v,S_2), \ldots, d(v, S_k))\). The \(k\)-partition \(\Pi\) is a resolving partition if the codes \(c_\Pi(v)\), \(v \in V(G)\), are distinct. A resolving partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) is acyclic if each subgraph \(\langle S_i \rangle\) induced by \(S_i\) (\(1 \leq i \leq k\)) is acyclic in \(G\). The minimum \(k\) for which there is a resolving acyclic \(k\)-partition of \(V(G)\) is the resolving acyclic number \(a_r(G)\) of \(G\). We study connected graphs with prescribed order, diameter, vertex-arboricity, and resolving acyclic number. It is shown that, for each triple \(d,k,n\) of integers with \(2 \leq d \leq n-2\) and \(3 \leq (n-d+1)/2 \leq k \leq n-d+1\), there exists a connected graph of order \(n\) having diameter \(d\) and resolving acyclic number \(k\). Also, for each pair \(a, b\) of integers with \(2 \leq a \leq b-1\), there exists a connected graph with resolving acyclic number \(a\) and vertex-arboricity \(b\). We present a sharp lower bound for the resolving acyclic number of a connected graph in terms of its clique number. The resolving acyclic number of the Cartesian product \(H \times K_2\) of nontrivial connected graph \(H\) and \(K_2\) is studied.