Forbidden graphs and irredundant perfect graphs (Q2721336)

A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma(G)\) of \(G\). For \(x\in V(G)\) the closed neighbourhood \(N[x]\) is the set consisting of \(x\) and of all vertices adjacent to \(x\). If \(X\subseteq V(G)\), then \(N[X]= \bigcup_{x\in X} N[x]\). The \(x\)-private neighbourhood \(\text{pn}(x,X)\) for \(x\in X\) is the set \(N[x]- N[X- \{x\}]\). A vertex \(x\in X\) is irredundant in \(X\), if \(\text{pn}(x, X)\) is not empty. If all vertices of \(X\) are irredundant, then \(X\) is called irredundant. The minimum number of vertices of a maximal irredundant set in \(G\) (with respect to set inclusion) is the irredundance number \(\text{ir}(G)\) of \(G\). The paper characterizes the pairs \((X,Y)\) of connected graphs with the property that for every graph \(G\) containing none of \(X\), \(Y\) as an induced subgraph, the equality \(\text{ir}(G)= \gamma(G)\) holds.