A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles

Abstract

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.