On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs

DOI10.1016/j.ejc.2008.07.022zbMath1200.05163OpenAlexW2151283714WikidataQ56859922 ScholiaQ56859922MaRDI QIDQ1024280

Michael W. Newman, Etienne de Klerk, Dimitrii V. Pasechnik, Renata Sotirov

Publication date: 17 June 2009

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejc.2008.07.022

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software, The independence number for polarity graphs of even order planes, Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming, Invariant Semidefinite Programs, A relative bound for independence, On the chromatic number of the Erdős-Rényi orthogonal polarity graph

Uses Software

• SeDuMi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Eigenvalue bounds for independent sets
• Graphs from projective planes
• Character tables of the association schemes of finite orthogonal groups acting on the nonisotropic points
• Graphs without quadrilaterals
• Symmetry groups, semidefinite programs, and sums of squares
• On the number of edges of quadrilateral-free graphs
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• On Graphs that do not Contain a Thomsen Graph