Stability, domination and irredundance in a graph

✍ Scribed by Odile Favaron

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 441 KB
• Volume: 10
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190100402

✦ Synopsis

In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V-X is joined to at least one vertex of X. A set Xis called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that is a vertex of V-Xjoined to it but to no other vertex of X. Let a' and a, y , and r, ir and IR, denote respectively the minimum and maximum cardinalities of a maximal stable set, a minimal dominating set, and a maximal irredundant set. It is known that ir s y s a' s (Y 4 1' s /Rand that if G does not contain any induced subgraph isomorphic to K,.3, then y = a'. Here we prove that if G contains no induced subgraph isomorphic to K3.3 or to the graph H of figure 1, then ir = y = a'. We prove also that if G contains no induced subgraph isomorphic to K,.3, to H, or to the graph h of figure 3, then I' = IR. Finally, we improve a result of Bollobas and Cockayne about sufficient conditions for y = ir in terms of forbidden su bg ra phs.