A disproof of Henning's conjecture on irredundance perfect graphs (Q1613565): Difference between revisions

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.