Irredundance perfect graphs

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

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 languageEnglish
Pages (from-to)107-120
Number of pages14
JournalDiscrete Mathematics
Volume142
Issue number1-3
DOIs
Publication statusPublished - 15 Jul 1995
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Irredundance perfect graphs'. Together they form a unique fingerprint.

Cite this