On the Lovász theta-number of almost regular graphs with application to Erdös--Rényi graphs

Etienne De Klerk (e.deklerkuvt.nl)
Michael W. Newman (m.newmanqmul.ac.uk)
Dmitrii V. Pasechnik (Dimantu.edu.sg)
Renata Sotirov (r.sotirovuvt.nl)

Abstract: We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta'-numbers of the graphs that result when the loop edges are removed. We show that the theta-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. Journal of Combinatorial Theory B, to appear]. As an application we compute the theta and theta'-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.Mathematical Programming B, to appear]. The computed values are strictly better than the Godsil-Newman eigenvalue bounds.

Keywords: Erdos-Renyi graph, stability number, Lovasz theta-number, Schrijver theta'-number, semidefinite programming

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: CentER Discussion Paper 2006-93 Tilburg University The Netherlands

Download: [PDF]

Entry Submitted: 09/28/2006
Entry Accepted: 09/28/2006
Entry Last Modified: 09/28/2006

Modify/Update this entry