A characterization of \(\Gamma\alpha(k)\)-perfect graphs
Let \(\pi \) and \(\tau \) be two arbitrary graph parameters that satisfy \(\pi (G)\geq \tau (G)\) for every graph \(G\). For any \(k\in N_{0}\) the class \(\pi \tau (k)\) is defined as the hereditary class of graphs that consists of all graphs \(G\) such that \(\pi (H)-\tau (H)\leq k\) for every induced subgraph \(H\) of \(G\). The elements of \(\pi \tau (k)\) are called \(\pi \tau (k)\)-perfect graphs. This concept was introduced by \textit{I. E. Zverovich} [J. Graph Theory 32, No. 3, 303-310 (1999; Zbl 0944.05073)] for the domination number \(\gamma \), the independent domination number \(i\) and the independence number \(\alpha \). Let \(\Gamma \) and IR denote the upper domination number and the upper irredundance number, respectively. The main aim of this paper is the characterization of \(\Gamma \alpha (k)\) in terms of forbidden induced subgraphs belonging to a class of graphs having five properties, which generalizes a recent result of \textit{G. Gutin} and \textit{V. E. Zverovich} [Discrete Math. 190, No. 1-3, 95-105 (1998; Zbl 0956.05077)] on upper domination perfect graphs, i.e., graphs in \(\Gamma \alpha (0)\). A number of known results on the classes \(\text{IR}\Gamma (0)\) and \(\Gamma \alpha (0)\) are extended to the classes \(\text{IR}\Gamma (k)\) and \(\Gamma \alpha (k)\).
scientific article; zbMATH DE number 1533354