## 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 language | English |
---|---|

Pages (from-to) | 416-433 |

Number of pages | 18 |

Journal | Journal of Combinatorial Optimization |

Volume | 36 |

Issue number | 2 |

DOIs | |

Publication status | Published - 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