A disproof of Henning's conjecture on irredundance perfect graphs
type: Item
instance of: scholarly article
title: A disproof of Henning's conjecture on irredundance perfect graphs
zbMATH Open document ID: 1008.05073
DOI: 10.1016/S0012-365X(01)00300-4
author: Lutz Volkmann
author: Vadim Zverovich
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: The paper leans on the following notions of finite simple undirected graphs. The domination number of a graph \(G\) is the minimum size of a vertex set \(X\) such that any vertex of \(G\) is either in \(X\) or is adjacent to some vertex of \(X\). Vertex set \(X\) is irredundant if for each vertex \(x\) of \(X\) either \(x\) is not adjacent to other vertices of \(X\) or there is a vertex \(v\) of \(V(G)-X\) such that \(v\) is adjacent only to \(x\) in \(X\). Irredundance number \(\text{ir}(G)\) is the minimum size of an inclusionwise maximal irredundant set of \(G\). A graph \(G\) is irredundance perfect if \(\gamma(H)=\text{ir}(H)\) for any spanned subgraph \(H\) of \(G\). After introducing some reladed notions, the authors survey some results on irredundance perfect graphs. They formulate Henning's conjecture saying that a graph \(G\) is irredundance perfect if each spanned subgraph \(H\) of \(G\) with \(\text{ir}(H)<5\) is irredundance perfect. The main result is a counterexample to this conjecture, namely a concrete minimal irredundance imperfect graph \(F^*\) with \(\text{ir}(F^*)=5\). (The authors seem to have a computer aided proof for the imperfection property.) The disproof of the conjecture is a labourious case check. The complexity result in the paper is that the irredundant set problem and the dominant set problem are both NP-complete for a certain subclass of irredundance perfect graphs. The article ends with some conjectures and problems.
reviewed by: Tamás Fleiner
Mathematics Subject Classification ID: 05C17
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1792480
zbMATH Keywords: domination number
zbMATH Keywords: irredundance number
zbMATH Keywords: irredundance perfect graph
Wikidata QID: Q123019300
MaRDI profile type: Publication
Recommended article: Proof of a conjecture on irredundance perfect graphs
Recommended article: Q5298905
Recommended article: Q4943531
Recommended article: Counterexamples to three conjectures concerning perfect graphs
Recommended article: Irredundance perfect graphs
Recommended article: Some conjectures on perfect graphs
Recommended article: On the perfect graph conjecture
Recommended article: Disproving a Conjecture on PI-Index of Graphs
Recommended article: Forbidden graphs and irredundant perfect graphs
Recommended article: A proof of Hougardy's conjecture for diamond-free graphs
description: scientific article; zbMATH DE number 1792480