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 the graph obtained from H by subdividing the edge e. We also introduce the class of G-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 G-perfect, provided that any graph obtained from H by subdividing a subset of its simplicial edges is G-perfect. In particular, we show that a large subclass of claw-free graphs is G-perfect, thus providing a partial answer to the well-known problem of finding a defining linear system for the stable set polytope of claw-free graphs.
Gear Composition of stable set polytopes and G-perfection
Galluccio A;Gentile C;
2009
Abstract
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 the graph obtained from H by subdividing the edge e. We also introduce the class of G-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 G-perfect, provided that any graph obtained from H by subdividing a subset of its simplicial edges is G-perfect. In particular, we show that a large subclass of claw-free graphs is G-perfect, thus providing a partial answer to the well-known problem of finding a defining linear system for the stable set polytope of claw-free graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
