2-clique-bond of stable set polyhedra

摘要

The 2-bond is a generalization of the 2-join where the subsets of nodes that are connected on each shore of the partition are not necessarily disjoint. If all the subsets are cliques we say that the 2-bond is a 2-clique-bond. The 2-clique-bond composition builds a graph G admitting a 2-clique-bond starting from two graphs G_1 and G_2. We prove that a linear description of the stable set polytope of G is obtained by properly composing the linear inequalities describing the stable set polytopes of G_1, G_2 and two other related graphs. We explain how to apply iteratively the 2-clique-bond composition to provide the complete linear description of the stable set polytope of new classes of graphs.