Published January 1, 2021 | Version v1
Journal article Open

Upper paired domination versus upper domination

  • 1. Gebze Tech Univ, Dept Comp Engn, Kocaeli, Turkey

Description

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

Files

bib-d5fec8c6-d9e9-4733-8d3b-f7e3e754fdca.txt

Files (145 Bytes)

Name Size Download all
md5:1a02d2085472c9890f8bdccb86e336e8
145 Bytes Preview Download