Upper paired domination versus upper domination
share
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 Γ(G), the maximum cardinality of a minimal paired dominating set in G is called the upper paired domination number of G, denoted by Γ_pr(G). We first show that Γ_pr(G)≤ 2Γ(G) for any graph G. We then focus on the graphs satisfying the equality Γ_pr(G)= 2Γ(G). We give characterizations for two special graph classes: bipartite and unicyclic graphs with Γ_pr(G)= 2Γ(G) by using the results of Ulatowski (2015). Besides, we study the graphs with Γ_pr(G)= 2Γ(G) and a restricted girth. In this context, we provide two characterizations: one for graphs with Γ_pr(G)= 2Γ(G) and girth at least 6 and the other for C_3-free cactus graphs with Γ_pr(G)= 2Γ(G). We also pose the characterization of the general case of C_3-free graphs with Γ_pr(G)= 2Γ(G) as an open question.
READ FULL TEXT