✦ LIBER ✦

A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets

✍ Scribed by A. Finbow; B. Hartnell; C. Whitehead

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 1003 KB
Volume: 125
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90156-2

No coin nor oath required. For personal study only.

✦ Synopsis

In 1970, Plummer introduced the notion of a well-covered graph as one in which every maximal independent set is a maximum.

Here, we study graphs in which there are exactly two sizes of maximal independent sets. A characterization of such graphs is obtained for graphs of girth eight or more.