A Characterisation of Well-Covered Cubic Graphs

Abstract

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.