2021/09/27 by Monique Laurent, Laurent, Monique, Luis Felipe Vargas +1 · 2 citations
Computer Science · Materials Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Graphene research and applications #Matrix Theory and Algorithms #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2109.12876
openalex publication_date 2021/09/27 · openalex created_date 2022/09/01 · openalex updated_date 2026/07/28
De Klerk and Pasechnik (2002) introduced the bounds ϑ(r)(G) (r∈ ℕ) for the stability number α(G) of a graph G and conjectured exactness at order α(G)-1: ϑ(α(G)-1)(G)=α(G). These bounds rely on the conic approximations Kn(r) by Parrilo (2000) for the copositive cone COPn. A difficulty in the convergence analysis of ϑ(r) is the bad behaviour of the cones Kn(r) under adding a zero row/column: when applied to a matrix not in K(0)n this gives a matrix not in any K(r)n+1, thereby showing strict inclusion \bigcupr≥ 0K(r)n⊂ COPn for n≥ 6. We investigate the graphs with ϑ(r)(G)=α(G) for r=0,1: we algorithmically reduce testing exactness of ϑ(0) to acritical graphs, we characterize critical graphs with ϑ(0) exact, and we exhibit graphs for which exactness of ϑ(1) is not preserved under adding an isolated node. This disproves a conjecture by Gvozdenović and Laurent (2007) which, if true, would have implied the above conjecture by de Klerk and Pasechnik.