| 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. |
