Upper paired domination versus upper domination

Abstract

A paired dominating set $P$ is a dominating set with the additional property that $P$ has a perfect matching. While the maximum cardainality of a minimal dominating set in a graph $G$ is called the upper domination number of $G$, denoted by $\Gamma (G)$, the maximum cardinality of a minimal paired dominating set in $G$ is called the upper paired domination number of $G$, denoted by ${\Gamma }_{pr}(G)$. By Henning and Pradhan (2019), we know that ${\Gamma }_{pr}(G)\le 2\Gamma (G)$ for any graph $G$ without isolated vertices. We focus on the graphs satisfying the equality ${\Gamma }_{pr}(G)=2\Gamma (G)$. We give characterizations for two special graph classes: bipartite and unicyclic graphs with ${\Gamma }_{pr}(G)=2\Gamma (G)$ by using the results of Ulatowski (2015). Besides, we study the graphs with ${\Gamma }_{pr}(G)=2\Gamma (G)$ and a restricted girth. In this context, we provide two characterizations: one for graphs with ${\Gamma }_{pr}(G)=2\Gamma (G)$ and girth at least 6 and the other for $C_3$-free cactus graphs with ${\Gamma }_{pr}(G)=2\Gamma (G)$. We also pose the characterization of the general case of $C_3$-free graphs with ${\Gamma }_{pr}(G)=2\Gamma (G)$ as an open question.