A characterization of (k)-perfect graphs

DOI10.1016/S0012-365X(00)00137-0MaRDI QIDQ1586777zbMATH OpenOpenAlexFDO

Authors Lothar Dohmen, Dieter Rautenbach, Lutz Volkmann

Publication date 10 December 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(00)00137-0

zbMATH Keywords

\(\Gamma \alpha (k)\)-perfect graphscharacterizationforbidden induced subgraphindependence numberperfect graphsupper domination numberupper irredundance number

Mathematics Subject Classification ID

Perfect graphs (05C17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

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)\).

Recommendations

• Upper domination and upper irredundance perfect graphs
• A semi-induced subgraph characterization of upper domination perfect graphs
• scientific article; zbMATH DE number 2073614
• k-Bounded classes of dominant-independent perfect graphs
• scientific article; zbMATH DE number 5844229

Cited in

(16)

• A characterization of normal fraternally orientable perfect graphs
• On \(\alpha_{r}\gamma_{s}(k)\)-perfect graphs
• Upper domination and upper irredundance perfect graphs
• A characterization of graphs G with G K^ 2(G)
• Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes
• scientific article; zbMATH DE number 2186993 (Why is no real title available?)
• scientific article; zbMATH DE number 5844229 (Why is no real title available?)
• Irredundance
• A semi-induced subgraph characterization of upper domination perfect graphs
• scientific article; zbMATH DE number 2073614 (Why is no real title available?)
• k-Bounded classes of dominant-independent perfect graphs
• A note on an induced subgraph characterization of domination perfect graphs
• Algorithmic Applications in Management
• A Sum of Squares Characterization of Perfect Graphs
• Some variations of perfect graphs
• \(\alpha \)-domination perfect trees

This page was built for publication: A characterization of \(\Gamma\alpha(k)\)-perfect graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1586777)