A characterization of well-covered graphs that contain neither 4- nor 5-cycles
✍ Scribed by A. Finbow; B. Hartnell; R. J. Nowakowski
- Publisher
- John Wiley and Sons
- Year
- 1994
- Tongue
- English
- Weight
- 434 KB
- Volume
- 18
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A graph is well covered if every maximal independent set has the same cardinality. A vertex x, in a well‐covered graph G, is called extendable if G – {x} is well covered and β(G) = β(G – {x}). If G is a connected, well‐covered graph containing no 4‐ nor 5‐cycles as subgraphs and G contains an extendable vertex, then G is the disjoint union of edges and triangles together with a restricted set of edges joining extendable vertices. There are only 3 other connected, well‐covered graphs of this type that do not contain an extendable vertex. Moreover, all these graphs can be recognized in polynomial time.