✦ LIBER ✦

Irredundance perfect andP6-free graphs

✍ Scribed by Puech, Jo�l

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 307 KB
Volume: 29
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199812)29:4<239::aid-jgt3>3.0.co;2-m

No coin nor oath required. For personal study only.

✦ Synopsis

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,

📜 SIMILAR VOLUMES

Irredundance in inflated graphs

✍ Favaron, Odile 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 263 KB

The inflation G I of a graph G with n(G) vertices and m(G) edges is obtained by replacing every vertex of degree d of G by a clique K d . We study the lower and upper irredundance parameters ir and IR of an inflation. We prove in particular that if γ denotes the domination number of a graph, γ(G I )

CO-irredundant Ramsey numbers for graphs

✍ E. J. Cockayne; G. MacGillivray; J. Simmons 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 120 KB 👁 1 views

Cycle-perfect graphs are perfect

✍ Le, Van Bang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB 👁 2 views

The cycle graph of a graph G is the edge intersection graph of the set of all the induced cycles of G. G is called cycle-perfect if G and its cycle graph have no chordless cycles of odd length at least five. We prove the statement of the title. 0 1996 John Wiley &

Coloring precolored perfect graphs

✍ Kratochv�l, Jan; Seb?, Andr�s 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

We consider the question of the computational complexity of coloring perfect graphs with some precolored vertices. It is well known that a perfect graph can be colored optimally in polynomial time. Our results give a sharp border between the polynomial and NP-complete instances, when precolored vert

On wing-perfect graphs

✍ Hougardy, Stefan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 1 views

An edge in a graph G is called a wing if it is one of the two nonincident edges of an induced P 4 (a path on four vertices) in G. For a graph G, its winggraph W (G) is defined as the graph whose vertices are the wings of G, and two vertices in W (G) are connected if the corresponding wings in G belo

On critically perfect graphs

✍ Wagler, Annegret 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 1 views

A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well-known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, a