Locally Well-Covered Graphs

Abstract

A graph G is called locally well-covered if there exists a vertex " E G such that each maximal stable set which contains " is a maximum stable set. We prove that every graph G which is not locally well-covered contains at least one of graphs G 1, G2, ... , Ge (Figure 1} as an induced subgraph. Hence the maximal hereditary subclass 1i.COCW£.C.C of locally well-covered graphs is characterized by the set { G1, G2, ... , G6} of minimal forbidden induced subgraphs. The class 1i.COCW£.C.C is polynomial-time recognizible and there is a polynomial-time algorithm for finding a maximum stable set, which is valid for every graph in the class 1i.COCW£.C.C. 2000 Mathematics Subject Classification: 05C85 (05C75, 68Ql5 68Q25 68Rl0}.