Abstract
The domination number γ(G) and the irredundance number ir(G) of a graph G have been considered by many authors. It is well known that ir(G) ≤ γ(G) holds for all graphs G. In this paper we investigate the concept of irredundance perfect graphs which deals with those graphs that have all their induced subgraphs H satisfying ir(H) = γ(H). We give a characterization of those graphs G for which ir(H) = γ(H) for every induced subgraph H of G with ir(H) = 2 in terms of 30 forbidden induced subgraphs. A sufficient condition for ir(G) = γ(G) for a graph G with ir(G) ≤ 4 is given in terms of three forbidden subgraphs. This result strengthens a conjecture due to Favaron (1986) which states that if a graph G does not contain these three forbidden subgraphs, then ir(G) = γ(G).
Original language | English |
---|---|
Pages (from-to) | 107-120 |
Number of pages | 14 |
Journal | Discrete Mathematics |
Volume | 142 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 15 Jul 1995 |
Externally published | Yes |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics