Abstract#R##N##R##N#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.
['Ramesh S Sankaranarayana', 'Lorna Stewart']
Complexity results for well-covered graphs