The stable set polytope and some operations on graphs Original Research Article

We study some operations on graphs in relation to the stable set polytope, for instance, identification of two nodes, linking a pair of nodes by an edge and composition of graphs by subgraph identification. We show that, with appropriate conditions, the descriptions of the stable set polytopes associated with the resulting graphs can be derived from those related to the initial graphs by adding eventual clique inequalities. Thus, perfection and h-perfection of graphs are preserved.