Stable Set Polytopes for a Class of Circulant Graphs
Geir Vaaland Dahl · SIAM Journal on Optimization · 1999
We study the stable set polytope P(G n ) for the graph G n with n nodes and edges [i,j] with $j \in \{i+1,i+2\}$, $i=1, \ldots, n$ and where nodes n+1 and 1 (resp., n+2 and 2) are identified. This graph coincides with the antiweb $\bar{W}(n,3)$. A minimal linear system defining P(G n ) is determined. The system consists of certain rank inequalities with some number theoretic flavor. A characterization of the vertices of a natural relaxation of P(G n ) is also given.