Please use this identifier to cite or link to this item: https://gnanaganga.inflibnet.ac.in:8443/jspui/handle/123456789/7628
Title: Locally Well-Covered Graphs
Authors: Zverovich
0 . Zverovich
Issue Date: 2005
Publisher: Bulletin of the Institute of Combinatorics and Its Applications
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}.
URI: http://gnanaganga.inflibnet.ac.in:8080/jspui/handle/123456789/7628
Appears in Collections:Articles to be qced

Files in This Item:
File SizeFormat 
LOCALLY WELL-COVERED GRAPHS.pdf
  Restricted Access
938.58 kBAdobe PDFView/Open Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.