 18 views
 8 downloads
Wellcovered graphs: some new subclasses and complexity results

 Author(s) / Creator(s)

Technical report TR9402. 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. Wellcovered graphs are of interest because while the problem of finding the size of a maximum independent set is NPcomplete for graphs in general, it is in P for wellcovered graphs. Many of the existing results in this area deal with characterizations of families of wellcovered 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 wellcovered 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 fillin, recognition, Steiner tree, and vertex cover. While most of the above problems prove to be as difficult for wellcovered 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 wellcovered graphs. This leads to the concept of a maximal intersection of independent sets. Based on this, a hierarchy of four new subclasses of wellcovered 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
 1994

 Subjects / Keywords

 Type of Item
 Report

 License
 Attribution 3.0 International