A semi-induced subgraph characterization of upper domination perfect graphs
✍ Scribed by Zverovich, Igor E.; Zverovich, Vadim E.
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 324 KB
- Volume
- 31
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantly perfect graphs, and circular arc graphs. In this article, we present a characterization of Γ-perfect graphs in terms of forbidden semi-induced subgraphs.
Key roles in the characterization are played by the odd prism and the even Möbius ladder, where the prism and the Möbius ladder are well-known 3-regular graphs [2]. Using the semi-induced subgraph characterization, we obtain a characterization