The structure of well-covered graphs and the complexity of their recognition problems
type: Item
instance of: scholarly article
title: The structure of well-covered graphs and the complexity of their recognition problems
zbMATH Open document ID: 0873.05074
author: David Tankus
author: Michael Tarsi
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-10-26T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1006762
zbMATH Keywords: independent sets
zbMATH Keywords: matchings
zbMATH Keywords: characterization
zbMATH Keywords: well-covered graphs
zbMATH Keywords: recognition
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: equimatchable graphs
MaRDI profile type: Publication
full work available at URL: jctb.1996.1742
OpenAlex ID: W2084977359
cites work: Recognizing Greedy Structures
cites work: Q3340896
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: WELL-COVERED GRAPHS: A SURVEY
cites work: Some covering concepts in graphs
cites work: Complexity results for well‐covered graphs
cites work: Well-covered claw-free graphs
DOI: 10.1006/JCTB.1996.1742
description: scientific article; zbMATH DE number 1006762