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,z)|z \in S\}\). 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 \(k\)-vectors \(c_\Pi(v), v \in V(G)\), are distinct. The minimum \(k\) for which there is a resolving \(k\)-partition of \(V(G)\) is the partition dimension \(pd(G)\) of \(G\). A resolving partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) of \(V(G)\) is a resolving-coloring if each \(S_i\) (\(1 \leq i \leq k\)) is independent and the resolving-chromatic number \(\chi_r(G)\) is the minimum number of colors in a resolving-coloring of \(G\). A resolving partition \(\Pi = \{S_1,S_2,\ldots,S_k\}\) is acyclic if each subgraph \((S_i)\) 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 \(\alpha_r(G)\) of \(G\). Thus \(2 \leq pd(G) < \alpha_r(G) \leq \chi_r(G) \leq n\) for every connected graph \(G\) of order \(n \geq 2\). We present bounds for the resolving acyclic number of a connected graph in terms of its arboricity, partition dimension, resolving-chromatic number, diameter, girth, and other parameters. Connected graphs of order \(n \geq 3\) having resolving acyclic number \(2, n,\) or \(n-1\) are characterized.