×

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

Summary: We consider \(k\)-regular graphs with loops, and study the Lovász \(\vartheta\)-numbers and Schrijver \(\vartheta'\)-numbers of the graphs that result when the loop edges are removed. We show that the \(\vartheta\)-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. Comb. Theory, Ser. B 98, No.4, 721–734 (2008; Zbl 1156.05041)].
As an application we compute the \(\vartheta\) and \(\vartheta'\) numbers of certain instances of Erdős-Rényi graphs. This computation exploits the graph symmetry using the methodology introduced in [{|it E. de Klerk}, D.V. Pasechnik and A. Schrijver, “Reduction of symmetric semidefinite programs using the regular \(*\)-representation,” Math. Program. 109, No.2-3 (B), 613–624 (2007; Zb; 05131080].
The computed values are strictly better than the Godsil-Newman eigenvalue bounds.

MSC:

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

Citations:

Zbl 1156.05041

Software:

SeDuMi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bannai, E.; Hao, S.; Song, S.-Y., Character tables of the association schemes of finite orthogonal groups acting on the nonisotropic points, J. Combin. Theory Ser. A, 54, 2, 164-200 (1990) · Zbl 0762.20005
[2] Brown, W. G., On graphs that do not contain a Thomsen graph, Canad. Math. Bull., 9, 281-285 (1966) · Zbl 0178.27302
[3] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press Inc. [Harcourt Brace Jovanovich Publishers]: Academic Press Inc. [Harcourt Brace Jovanovich Publishers] New York · Zbl 0458.05042
[4] Delsarte, P., An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., 10, vi+97 (1973) · Zbl 1075.05606
[5] Erdós, P.; Rényi, A.; Sós, V. T., On a problem of graph theory, Studia Sci. Math. Hungar., 1, 215-235 (1966) · Zbl 0144.23302
[6] Füredi, Z., Graphs without quadrilaterals, J. Combin. Theory Ser. B, 34, 2, 187-190 (1983) · Zbl 0505.05038
[7] Füredi, Z., On the number of edges of quadrilateral-free graphs, J. Combin. Theory Ser. B, 68, 1, 1-6 (1996) · Zbl 0858.05063
[8] de Klerk, E.; Pasechnik, D. V.; Schrijver, A., Reduction of symmetric semidefinite programs using the regular *-representation, Math. Program. B, 109, 2-3, 613-624 (2007) · Zbl 1200.90136
[9] Gatermann, K.; Parrilo, P. A., Symmetry groups, semidefinite programs, and sum of squares, J. Pure Appl. Algebra, 192, 95-128 (2004) · Zbl 1108.13021
[10] Godsil, C. D.; Newman, M. W., Eigenvalue bounds for independent sets, J. Combin. Theory B, 98, 4, 721-734 (2008) · Zbl 1156.05041
[11] Hirschfeld, J. W.P., Projective geometry over finite fields (1998), Clarendon Press: Clarendon Press Oxford · Zbl 0899.51002
[12] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1-7 (1979) · Zbl 0395.94021
[13] Lovász, L.; Schrijver, A., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 2, 166-190 (1991) · Zbl 0754.90039
[14] Mubayi, D.; Williford, J., On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph, J. Graph Theory, 56, 2, 113-127 (2007) · Zbl 1128.05040
[15] Parsons, T. D., Graphs from projective planes, Aequationes Math., 14, 1-2, 167-189 (1976) · Zbl 0323.05116
[16] Schrijver, A., A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inform. Theory, 25, 425-429 (1979) · Zbl 0444.94009
[17] Sturm, J. F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 11-12, 625-653 (1999) · Zbl 0973.90526
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.