  


On the Lovász thetanumber of almost regular graphs with application to ErdösRényi graphs
Etienne De Klerk (e.deklerkuvt.nl) Abstract: We consider kregular graphs with loops, and study the Lovász thetanumbers and Schrijver theta'numbers of the graphs that result when the loop edges are removed. We show that the thetanumber 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ösRé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 GodsilNewman eigenvalue bounds. Keywords: ErdosRenyi graph, stability number, Lovasz thetanumber, Schrijver theta'number, semidefinite programming Category 1: Combinatorial Optimization (Graphs and Matroids ) Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: CentER Discussion Paper 200693 Tilburg University The Netherlands Download: [PDF] Entry Submitted: 09/28/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  