Complexity results for well‐covered graphs

Abstract

Abstract A graph with n vertices is well covered if every maximal independent set is a maximum independent set and very well covered if every maximal independent set has size n /2. In this work, we study these graphs from an algorithmic complexity point of view. We show that well‐covered graph recognition is co‐NP‐complete and that several other problems are NP‐complete for well‐covered graphs. A number of these problems remain NP‐complete on very well covered graphs, while some admit polynomial time solutions for the smaller class. For both families, the isomorphism problem is as hard as general graph isomorphism.