A semi-induced subgraph characterization of upper domination perfect graphs
Igor É. Zverovich, Vadim E. Zverovich · Journal of Graph Theory · 1999
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, absobantly 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 of K1,3-free Γ-perfect graphs in terms of forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:29–49, 1999