کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4654356 | 1632821 | 2009 | 10 صفحه PDF | دانلود رایگان |
We consider kk-regular graphs with loops, and study the Lovász ϑϑ-numbers and Schrijver ϑ′ϑ′-numbers of the graphs that result when the loop edges are removed. We show that the ϑϑ-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets, J. Combin. Theory B 98 (4) (2008) 721–734].As an application we compute the ϑϑ and ϑ′ϑ′ numbers of certain instances of Erdős–Rényi graphs. This computation exploits the graph symmetry using the methodology introduced in [E. de Klerk, D.V. Pasechnik and A. Schrijver, Reduction of symmetric semidefinite programs using the regular *-representation, Math. Program. B 109 (2–3) (2007) 613–624].The computed values are strictly better than the Godsil–Newman eigenvalue bounds.
Journal: European Journal of Combinatorics - Volume 30, Issue 4, May 2009, Pages 879–888