Semipaired domination in maximal outerplanar graphs

Michael A. Henning, Pawaton Kaemawichanurat

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

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 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 semipaired domination number γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. Let G be a maximal outerplanar graph of order n with n2 vertices of degree 2. We show that if n≥ 5 , then γpr2(G)≤25n. Further, we show that if n≥ 3 , then γpr2(G)≤13(n+n2). Both bounds are shown to be tight.

Original languageEnglish
Pages (from-to)911-926
Number of pages16
JournalJournal of Combinatorial Optimization
Volume38
Issue number3
DOIs
Publication statusPublished - 15 Oct 2019

Keywords

  • Maximal outerplanar graphs
  • Paired-domination
  • Semipaired domination number

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Semipaired domination in maximal outerplanar graphs'. Together they form a unique fingerprint.

Cite this