Download the full-sized PDF of Well-covered graphs: some new sub-classes and complexity resultsDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Computing Science, Department of


This file is in the following collections:

Technical Reports (Computing Science)

Well-covered graphs: some new sub-classes and complexity results Open Access


Author or creator
Sankaranarayana, Ramesh
Additional contributors
very well covered graphs
complexity results
Well-covered graphs
new sub-classes
Type of item
Technical report TR94-02. A graph is said to be well covered if every maximal independent set has the same size, and very well covered if every maximal independent set contains exactly half the vertices in the graph. Well-covered graphs are of interest because while the problem of finding the size of a maximum independent set is NP-complete for graphs in general, it is in P for well-covered graphs. Many of the existing results in this area deal with characterizations of families of well-covered graphs. This thesis focuses on the algorithmic properties of this family. The first part of this thesis looks at the algorithmic complexities of the following problems for the families of well-covered and very well covered graphs: chromatic number, clique cover, clique partition, dominating cycle, dominating set, Hamiltonian cycle, Hamiltonian path, independent set, independent dominating set, maximum cut, minimum fill-in, recognition, Steiner tree, and vertex cover. While most of the above problems prove to be as difficult for well-covered graphs as for graphs in general, a number of them become tractable when restricted to the family of very well covered graphs. In the second part of this thesis, an alternative characterization is given for the family of well-covered graphs. This leads to the concept of a maximal intersection of independent sets. Based on this, a hierarchy of four new sub-classes of well-covered graphs is defined. The families are characterized and the algorithmic complexities of the above mentioned problems are studied for these families. It is also shown that the last class in the hierarchy is exactly the family of very well covered graphs without isolated vertices. A generalization of Favaron's theorem for very well covered graphs is also proved.
Date created
License information
Creative Commons Attribution 3.0 Unported

Citation for previous publication

Link to related item

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1435052
Last modified: 2016:08:04 02:55:53-06:00
Filename: TR94-02.pdf
Original checksum: 16de946290eda2a4a0119a67948493f6
Well formed: true
Valid: true
Page count: 94
Activity of users you follow
User Activity Date