A Characterisation of Well-Covered Cubic Graphs

A graph is said to be \({well-covered}\) if all maximal independent sets of vertices in the graph have the same cardinality. Determining whether a graph is well-covered has recently been shown (independently by Chvátal and Slater and by Sankaranarayana and Stewart) to be a co-NP-complete problem. In this paper, we characterise all well-covered cubic (\(3\)-regular) graphs. Our characterisation yields a polynomial time algorithm for recognising well-covered cubic graphs.