This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  2007, with author Ventura P., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 661  (Previous    Next)  

Anna Galluccio, Claudio Gentile, Paolo Ventura

Gear composition of stable set polytopes and G-perfection

ABSTRACT

Graphs obtained by repeated applications of 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: rank inequalities, lifted 5-wheel inequalities and some special inequalities called geared inequalities and g-lifted inequalities. We show that some classes of graphs are G-perfect. In particular, we prove 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.