Back to Search
Start Over
Upper paired domination versus upper domination.
- Source :
-
Discrete Mathematics & Theoretical Computer Science (DMTCS) . 2021, Vol. 23 Issue 3, p1-16. 16p. - Publication Year :
- 2021
-
Abstract
- 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 Γ(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). By Henning and Pradhan (2019), we know that Γpr(G) ≤ 2Γ(G) for any graph G without isolated vertices. We 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 C3-free cactus graphs with Γpr(G) = 2Γ(G). We also pose the characterization of the general case of C3-free graphs with Γpr(G) = 2Γ(G) as an open question. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- 23
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics & Theoretical Computer Science (DMTCS)
- Publication Type :
- Academic Journal
- Accession number :
- 155291090