Premium
Irredundance perfect and P 6 ‐free graphs
Author(s) -
Puech Joël
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199812)29:4<239::aid-jgt3>3.0.co;2-m
Subject(s) - combinatorics , mathematics , cograph , strong perfect graph theorem , perfect graph theorem , split graph , trivially perfect graph , discrete mathematics , graph , pathwidth , line graph
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 , which leads us to consider the concept of irredundance perfect graphs: graphs that have all their induced subgraphs satisfying the equality between the previous two parameters. In this article, we investigate two subclasses of irredundance perfect graphs that are defined in terms of forbidden subgraphs, where in each case, one of the forbidden subgraphs is the path P 6 . In particular, we prove two conjectures, the first one due to Faudree, Favaron, and Li [Faudree et al., J Combin. Math., 1997], and the second one due to Favaron [Favaron, J Graph Theory, 1986]. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 239–255, 1998