A characterization of \(\Gamma\alpha(k)\)-perfect graphs
type: Item
instance of: scholarly article
title: A characterization of \(\Gamma\alpha(k)\)-perfect graphs
zbMATH Open document ID: 0976.05042
DOI: 10.1016/S0012-365X(00)00137-0
author: Lothar Dohmen
author: Dieter Rautenbach
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 2001-12-10T00:00:00Z
review text: 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)\).
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1533354
zbMATH Keywords: upper domination number
zbMATH Keywords: independence number
zbMATH Keywords: upper irredundance number
zbMATH Keywords: \(\Gamma \alpha (k)\)-perfect graphs
zbMATH Keywords: forbidden induced subgraph
zbMATH Keywords: perfect graphs
zbMATH Keywords: characterization
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00137-0
OpenAlex ID: W2074204978
description: scientific article; zbMATH DE number 1533354