Connected partition dimensions of graphs (Q4435566)

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)\mid x\in S\}\). For an ordered \(k\)-partition \(\Pi =\{S_{1},\dots ,S_{k}\}\) of \(V(G)\), the representation of \(v\) with respect to \(\Pi \) is the \(k\)-vector \(r(v|\Pi)=(d(v,S_{1}),\dots ,d(v,S_{k}))\). The \(k\)-partition \(\Pi \) is said to be a resolving partition 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 \(\text{pd}(G)\) of \(G\). A resolving partition is said to be connected if each subgraph induced by \(S_{i}\) is connected in \(G\) for each \(i\) with \(1\leq i\leq k\) and the corresponding parameter is called the connected partition dimension \(\text{cpd}(G)\) of \(G\). Thus \(2\leq \text{pd}(G)\leq \text{cpd}(G)\leq n\) for every connected graph \(G\) of order \(n\geq 2\). In this paper the connected partition dimensions of several classes of well-known graphs (complete, complete bipartite, paths, trees) are determined. It is shown that for every pair \(a,b\) of integers with \(3\leq a\leq b\leq 2a-1\), there is a connected graph \(G\) having \(\text{pd}(G)=a\) and \(\text{cpd}(G)=b\). Also connected graphs of order \(n\geq 3\) having connected partition dimension \(2,n\), or \(n-1\) are characterized.