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  2009, with author Gentile C., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 09-05  (Next)  

Anna Galluccio, Claudio Gentile, Paolo Ventura

The stable set polytope of claw-free graphs I: XX-strip composition versus gear composition

ABSTRACT

The gear composition builds a new graph G by substituting a suitable edge of a given graph H with a fixed graph named gear. Here we extend this definition to obtain an operation that is suitable to handle claw-free graphs. We call geared (fuzzy) line graphs the graphs obtained from (fuzzy) line graphs by repeated applications of the extended gear composition and we prove that these graphs form a significant subclass of claw-free graphs with stability number at least four. The proof is based on the decomposition theorem of Chudnovsky and Seymour. We also show how the extended gear composition generates facet defining inequalities for the stable set polytope of a geared graph G. In a sequel we prove that these facet defining inequalities yield the complete linear description of the stable set polytope of geared (fuzzy) line graphs.