Exactness of Parrilo's conic approximations for copositive matrices >> and associated low order bounds for the stability number of a graph

De Klerk and Pasechnik introduced in 2002 semidefinite bounds ϑ ^(r)(G)(r ≥ 0) for the stability number α(G) of a graph G and conjectured their exactness at order r = α(G) − 1. These bounds rely on the conic approximations K ⁽ _n ^r) introduced by Parrilo in 2000 for the copositive cone COP _n. A difficulty in the convergence analysis of the bounds is the bad behavior of Parrilo’s cones under adding a zero row/column: when applied to a matrix not in K ⁽ _n ^r) this gives a matrix that does not lie in any of Parrilo’s cones, thereby showing that their union is a strict subset of the copositive cone for any n ≥ 6. We investigate the graphs for which the bound of order r ≤ 1 is exact: we algorithmically reduce testing exactness of ϑ ⁽⁰⁾ to acritical graphs, we characterize the critical graphs with ϑ ⁽⁰⁾ exact, and we exhibit graphs for which exactness of ϑ ⁽¹⁾ is not preserved under adding an isolated node. This disproves a conjecture posed by Gvozdenović and Laurent in 2007, which, if true, would have implied the above conjecture by de Klerk and Pasechnik.