The structure of well-covered graphs and the complexity of their recognition problems (Q1354731)

A graph is well covered if all its maximal independent sets are of the same cardinality. Deciding whether a given graph is well covered is known to be NP-hard in general. A graph is equimatchable if all its maximal matchings are maximum. Clearly, a graph is equimatchable if and only if its line-graph is well covered. The authors present a simple structural characterization of well-covered graphs and then apply it to the recognition problem. They present a new polynomial time algorithm for the case where the input graph contains no induced subgraph isomorphic to \(K_{1,3}\). Considering the line-graph of an input graph, this result provides a short and simple alternative to a proof of \textit{M. Lesk}, \textit{M. D. Plummer} and \textit{W. R. Pulleyblank}, who showed that equimatchable graphs can be recognized in polynomial time [Graph theory and combinatorics, Proc. Conf. Hon. P. Erdös, Cambridge 1983, 239-254 (1984; Zbl 0548.05048)].