Maximal outerplanar graphs with semipaired domination number double the domination number

Michael A. Henning, Pawaton Kaemawichanurat

Research output: Contribution to journalArticlepeer-review

Abstract

A subset S of vertices in a graph G is a dominating set if every vertex in V (G) \ S is adjacent to a vertex in S. If the graph G has no isolated vertex, then a paired dominating set S of G is a dominating set of G such that G[S] has a perfect matching. Further, a semipaired dominating set of G is a dominating set of G with the additional property that the set S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The domination number γ(G) is the minimum cardinality of a dominating set of G. Similarly, the paired (semipaired) domination number γpr(G) (γpr2(G)) is the minimum cardinality of a paired (semipaired) dominating set of G. It is known that for a graph G, γ(G) ≤ γpr2(G) ≤ γpr(G) ≤ 2γ(G). In this paper, we characterize maximal outerplanar graphs G satisfying γpr2(G) = 2γ(G). Hence, our result yields the characterization of maximal outerplanar graphs G satisfying γpr(G) = 2γ(G).

Original languageEnglish
Pages (from-to)1-20
Number of pages20
JournalCommunications in Combinatorics and Optimization
Volume11
Issue number1
DOIs
Publication statusPublished - Mar 2026

Keywords

  • graphs paired-domination
  • maximal outerplanar
  • semipaired domination number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Maximal outerplanar graphs with semipaired domination number double the domination number'. Together they form a unique fingerprint.

Cite this