Premium
A semi‐induced subgraph characterization of upper domination perfect graphs
Author(s) -
Zverovich Igor E.,
Zverovich Vadim E.
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199905)31:1<29::aid-jgt4>3.0.co;2-g
Subject(s) - combinatorics , mathematics , cograph , induced subgraph , split graph , chordal graph , characterization (materials science) , trivially perfect graph , distance hereditary graph , discrete mathematics , indifference graph , strong perfect graph theorem , block graph , perfect graph , pathwidth , graph , line graph , 1 planar graph , voltage graph , physics , vertex (graph theory) , optics
Abstract 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 K 1,3 ‐free Γ‐perfect graphs in terms of forbidden induced subgraphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:29–49, 1999