De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{ (r)}(G)$ ($r\in \mathbb{ N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{ (\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{ K}_n^{ (r)}$ by Parrilo (2000) for the copositive cone $\text{ COP}_n$. A difficulty in the convergence analysis of $\vartheta^{ (r)}$ is the bad behaviour of the cones $\mathcal{ K}_n^{ (r)}$ under adding a zero row/column: when applied to a matrix not in $\mathcal{ K}^{ (0)}_n$ this gives a matrix not in any ${ \mathcal{ K}}^{ (r)}_{ n+1}$, thereby showing strict inclusion $\bigcup_{ r\ge 0}{ \mathcal{ K}}^{ (r)}_n\subset \text{ COP}_n$ for $n\ge 6$. We investigate the graphs with $\vartheta^{ (r)}(G)=\alpha(G)$ for $r=0,1$: we algorithmically reduce testing exactness of $\vartheta^{ (0)}$ to acritical graphs, we characterize critical graphs with $\vartheta^{ (0)}$ exact, and we exhibit graphs for which exactness of $\vartheta^{ (1)}$ is not preserved under adding an isolated node. This disproves a conjecture by Gvozdenovi\'c and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.
Categories: math.OC math.CO