Perfect graphs involving semitotal and semipaired domination

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

Abstract

Let G be a graph with vertex set V and no isolated vertices, and let S be a dominating set of V. The set S is a semitotal dominating set of G if every vertex in S is within distance 2 of another vertex of S. And, S is a semipaired dominating set of G if S can be partitioned into 2-element subsets such that the vertices in each 2-set are at most distance two apart. The semitotal domination number γt 2(G) is the minimum cardinality of a semitotal dominating set of G, and the semipaired domination number γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. For a graph without isolated vertices, the domination number γ(G) , the total domination γt(G) , and the paired domination number γpr(G) are related to the semitotal and semipaired domination numbers by the following inequalities: γ(G) ≤ γt 2(G) ≤ γt(G) ≤ γpr(G) and γ(G) ≤ γt 2(G) ≤ γpr 2(G) ≤ γpr(G) ≤ 2 γ(G). Given two graph parameters μ and ψ related by a simple inequality μ(G) ≤ ψ(G) for every graph G having no isolated vertices, a graph is (μ, ψ) -perfect if every induced subgraph H with no isolated vertices satisfies μ(H) = ψ(H). Alvarado et al. (Discrete Math 338:1424–1431, 2015) consider classes of (μ, ψ) -perfect graphs, where μ and ψ are domination parameters including γ, γt and γpr. We study classes of perfect graphs for the possible combinations of parameters in the inequalities when γt 2 and γpr 2 are included in the mix. Our results are characterizations of several such classes in terms of their minimal forbidden induced subgraphs.

Original languageEnglish
Pages (from-to)416-433
Number of pages18
JournalJournal of Combinatorial Optimization
Volume36
Issue number2
DOIs
Publication statusPublished - 1 Aug 2018

Keywords

  • Paired-domination
  • Perfect graphs
  • Semipaired domination
  • Semitotal domination

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 'Perfect graphs involving semitotal and semipaired domination'. Together they form a unique fingerprint.

Cite this