This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Galluccio, A. Articles by Ventura, P.

Gear Composition of Stable Set Polytopes and -Perfection

Istituto di Analisi dei Sistemi ed Informatica "A. Ruberti," CNR, 00185 Rome, Italy
Istituto di Analisi dei Sistemi ed Informatica "A. Ruberti," CNR, 00185 Rome, Italy
Istituto di Analisi dei Sistemi ed Informatica "A. Ruberti," CNR, 00185 Rome, Italy
galluccio{at}iasi.cnr.it
gentile{at}iasi.cnr.it
ventura{at}iasi.cnr.it

Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB(H) and STAB(H^e), where H^e is the graph obtained from H by subdividing the edge e. We also introduce the class of -perfect graphs, i.e., graphs whose stable set polytope is described by nonnegativity inequalities, rank inequalities, lifted 5-wheel inequalities, and some special inequalities called geared inequalities and g-lifted inequalities. We prove that graphs obtained by repeated applications of the gear composition to a given graph H are -perfect, provided that any graph obtained from H by subdividing a subset of its simplicial edges is -perfect. In particular, we show that a large subclass of claw-free graphs is -perfect.

Key Words: stable set polytope; graph composition; polyhedral combinatorics
History: Received: July 28, 2008; revision received: January 28, 2009;