- 192 views
- 144 downloads
Well-covered graphs: some new sub-classes and complexity results
-
- Author(s) / Creator(s)
-
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
- 1994
-
- Subjects / Keywords
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International