Forbidden Graphs and Irredundant Perfect Graphs

Joél Puech1
1Mathématique, Bat. 425, Université Paris-Sud, 91405 Orsay cedex, France

Abstract

The domination number \(\gamma(G)\) and the irredundance number \(ir(G)\) of a graph \(G\) have been considered by many authors. It is well known that \(ir(G) \leq \gamma(G)\) holds for all graphs \(G\). In this paper we determine all pairs of connected graphs \((X, Y)\) such that every graph \(G\) containing neither \(X\) nor \(Y\) as an induced subgraph satisfies \(ir(G) = \gamma(G)\).