Optimization Online


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

Etienne De Klerk (e.deklerk***at***uvt.nl)
Michael W. Newman (m.newman***at***qmul.ac.uk)
Dmitrii V. Pasechnik (Dima***at***ntu.edu.sg)
Renata Sotirov (r.sotirov***at***uvt.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society