2 2 -clique-bond of stable set polyhedra
The 2 2 -bond is a generalization of the 2 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 2 -clique-bond. The 2 2 -clique-bond composition builds a graph G G admitting a 2-clique-bond starting from two graphs G1 G 1 and G2 G 2 . We prove that a linear description of the stable set polytope of G G is obtained by properly composing the linear inequalities describing the stable set polytopes of G1 G 1 , G2 G 2 and two other related graphs. We explain how to apply iteratively the 2 2 -clique-bond composition to provide the complete linear description of the stable set polytope of new classes of graphs.
stable set polytope graph compositions 2-join polyhedral combinatorics