Back to Search
Start Over
On the Lovász -number of almost regular graphs with application to Erdős–Rényi graphs
- Source :
-
European Journal of Combinatorics . May2009, Vol. 30 Issue 4, p879-888. 10p. - Publication Year :
- 2009
-
Abstract
- Abstract: We consider -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. [Copyright &y& Elsevier]
- Subjects :
- *MATRICES (Mathematics)
*GRAPHIC methods
*LEAST squares
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 30
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 36893617
- Full Text :
- https://doi.org/10.1016/j.ejc.2008.07.022