Premium
Complexity results for well‐covered graphs
Author(s) -
Sankaranarayana Ramesh S.,
Stewart Lorna K.
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220304
Subject(s) - combinatorics , graph isomorphism , maximal independent set , mathematics , independent set , induced subgraph isomorphism problem , discrete mathematics , pathwidth , time complexity , split graph , graph automorphism , computational complexity theory , graph , indifference graph , chordal graph , 1 planar graph , line graph , algorithm , voltage graph
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.