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 G1 and G2. 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 G1, G2 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.
2-clique-bond of stable set polyhedra
A Galluccio;C Gentile;P Ventura
2013
Abstract
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 G1 and G2. 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 G1, G2 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
