On the Partition Dimension and Connected Partition Dimension of Wheels

Abstract

Let \(G\) be a connected graph. For a vertex \(v \in V(G)\) and an ordered \(k\)-partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) of \(V(G)\), the representation of \(v\) with respect to \(\Pi\) is the \(k\)-vector \(r(v|\Pi) = (d(v, S_1), d(v, S_2), \ldots, d(v, S_k))\). The \(k\)-partition \(\Pi\) is said to be resolving if the \(k\)-vectors \(r(v|\Pi), v \in V(G)\), are distinct. The minimum \(k\) for which there is a resolving \(k\)-partition of \(V(G)\) is called the partition dimension of \(G\), denoted by \(pd(G)\). A resolving \(k\)-partition \(\Pi = \{S_1, S_2, \ldots, S_k\}\) of \(V(G)\) is said to be connected if each subgraph \(\langle S_i \rangle\) induced by \(S_i\) (\(1 \leq i \leq k\)) is connected in \(G\). The minimum \(k\) for which there is a connected resolving \(k\)-partition of \(V(G)\) is called the connected partition dimension of \(G\), denoted by \(cpd(G)\). In this paper, the partition dimension as well as the connected partition dimension of the wheel \(W_n\) with \(n\) spokes are considered, by showing that \(\lceil (2n)^{1/3} \rceil \leq pd(W_n) \leq \lceil 2(n)^{1/2} \rceil +1\) and \(cpd(W_n) = \lceil (n+2)/3 \rceil\) for \(n \geq 4\).