Perfect Graphs Involving Semitotal and Semipaired Domination
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.
Haynes, Teresa W.; and Henning, Michael A.. 2018. Perfect Graphs Involving Semitotal and Semipaired Domination. Journal of Combinatorial Optimization. Vol.36(2). 416-433. https://doi.org/10.1007/s10878-018-0303-9 ISSN: 1382-6905