On the Lovász ϑ-number of almost regular graphs with application to Erdős–Rényi graphs

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. Newma...

Full description

Saved in:
Bibliographic Details
Main Authors: Sotirov, R., Klerk, Etienne de., Newman, M. W., Pasechnik, Dmitrii V.
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2012
Subjects:
Online Access:https://hdl.handle.net/10356/94538
http://hdl.handle.net/10220/7516
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary: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.