Back to Search Start Over

Recognizing Well Covered Graphs of Families with Special P 4-Components

Authors :
Célia Picinin de Mello
Sulamita Klein
Aurora Morgana
Source :
Graphs and Combinatorics. 29:553-567
Publication Year :
2011
Publisher :
Springer Science and Business Media LLC, 2011.

Abstract

A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper we shall use the modular and primeval decomposition techniques to decide well coveredness of graphs such that, either all their P 4-connected components (in short, P 4-components) are separable or they belong to well known classes of graphs that, in some local sense, contain few P 4's. In particular, we shall consider the class of cographs, P 4-reducible, P 4-sparse, extended P 4-reducible, extended P 4-sparse graphs, P 4-extendible graphs, P 4-lite graphs, and P 4-tidy graphs.

Details

ISSN :
14355914 and 09110119
Volume :
29
Database :
OpenAIRE
Journal :
Graphs and Combinatorics
Accession number :
edsair.doi...........01d8f13130feca8be64b5909c0448931
Full Text :
https://doi.org/10.1007/s00373-011-1123-1