Resolving dominating partitions in graphs

Abstract

A partition $\Pi =\{S_1,\dots ,S_k\}$ of the vertex set of a connected graph $G$ is called a \emph{resolving partition} of $G$ if for every pair of vertices $u$ and $v$, $d(u,S_j)\ne d(v,S_j)$, for some part $S_j$. The \emph{partition dimension} ${\beta }_p(G)$ is the minimum cardinality of a resolving partition of $G$. A resolving partition $\Pi$ is called \emph{resolving dominating} if for every vertex $v$ of $G$, $d(v,S_j)=1$, for some part $S_j$ of $\Pi$. The \emph{dominating partition dimension} ${\eta }_p(G)$ is the minimum cardinality of a resolving dominating partition of $G$. In this paper we show, among other results, that ${\beta }_p(G)\le {\eta }_p(G)\le {\beta }_p(G)+1$. We also characterize all connected graphs of order $n\ge 7$ satisfying any of the following conditions: ${\eta }_p(G)=n$, ${\eta }_p(G)=n-1$, ${\eta }_p(G)=n-2$ and ${\beta }_p(G)=n-2$. Finally, we present some tight Nordhaus-Gaddum bounds for both the partition dimension ${\beta }_p(G)$ and the dominating partition dimension ${\eta }_p(G)$.

22 pages, 9 figures