Please use this identifier to cite or link to this item:
|Title:||On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs||Authors:||Sotirov, R.
Klerk, Etienne de.
Newman, M. W.
Pasechnik, Dmitrii V.
|Keywords:||DRNTU::Science::Mathematics||Issue Date:||2008||Source:||Klerk, E. D., Newman, M. W., Pasechnik, D. V. & Sotirov R. (2009). On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs. European Journal of Combinatorics, 30(4), 879–888||Series/Report no.:||European journal of combinatorics||Abstract:||We consider k-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.||URI:||https://hdl.handle.net/10356/94538
|DOI:||10.1016/j.ejc.2008.07.022||Rights:||© 2008 Elsevier. This is the author created version of a work that has been peer reviewed and accepted for publication by European Journal of Combinatorics, Elsevier. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [DOI: http://dx.doi.org/10.1016/j.ejc.2008.07.022 ]||Fulltext Permission:||open||Fulltext Availability:||With Fulltext|
|Appears in Collections:||SPMS Journal Articles|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.