Well-covered graphs and factors

Bert Randerath, Preben D. Vestergaard

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

4 Citationer (Scopus)


A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. Every well-covered graph G without isolated vertices has a perfect [1,2]-factor F_G, i.e. a spanning subgraph such that each component is 1-regular og 2-regular. Here, we characterize all well-covered graphs G satisfying α(G)=α(F_G) for some perfect [1,2]-factor F_G. This class contains all well-covered graphs G without isolated vertices of order n with α ≥ (n - 1)/2, and in particular all very well-covered graphs.
Udgivelsesdato: JUN 1
TidsskriftDiscrete Applied Mathematics
Udgave nummer9
Sider (fra-til)1416-1428
Antal sider13
StatusUdgivet - 2006

Fingeraftryk Dyk ned i forskningsemnerne om 'Well-covered graphs and factors'. Sammen danner de et unikt fingeraftryk.