The disjunctive rank of the stable set polytope of web graphs

BIANCHI, SILVIA MARIA; ESCALANTE, MARIANA SILVINA; MONTELAR, MARÍA SUSANA

Berlin

Simposio; 21st International Symposium on Mathematical Programming; 2012

Mathematical Programming

We consider the disjunctive operator defined by Balas, Ceria and Cornuejols over the clique relaxation of th stable set polytope on web graphs. It is known that this rank coincides with the minimum number of nodes that must be deleted for the graph being perfect. This shows an upper bound for the disjunctive rank of any web graph. In this work we found the disjunctive rank of any web graph W^k_n and prove that the upper bound k is achieved except for the graphs W^k_{3k+r} for r = 0 and r = 1, where the ranks are, respectively, k - 2 and k - 1. Our results allow us to estimate bounds for the disjunctive rank of more general classes of graphs as quasi-line graphs and their complements, the near-bipartite ones.