Spectral Characterizations of the Lovász Number and the Delsarte Number of a Graph
A. Galtman
DOI: 10.1023/A:1026587926110
Abstract
This paper gives spectral characterizations of two closely related graph functions: the Lovász number 
and a generalization 1 of Delsarte's linear programming bound. There are many known characterizations of the Lovász number , and each one corresponds to a similar characterization of 1 obtained by extremizing over a larger or smaller class of objects.
and a generalization 1 of Delsarte's linear programming bound. There are many known characterizations of the Lovász number , and each one corresponds to a similar characterization of 1 obtained by extremizing over a larger or smaller class of objects. The spectral characterizations of and 1 given here involve the largest eigenvalue of a type of weighted Laplacian that Fan Chung introduced.
and 1 given here involve the largest eigenvalue of a type of weighted Laplacian that Fan Chung introduced.Pages: 131–143
Keywords: graph Laplacian; delsarte linear programming bound; lovász number
Full Text: PDF
References
1. F.R.K. Chung, Spectral Graph Theory, AMS Publications, Providence, R.I.,
1996. CBMS Lecture Notes.
2. M. Gr\ddot otschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd edition, Section 9.3, Springer-Verlag, Berlin, 1993.
3. A.H. Hoffman, “Eigenvalues of graphs,” in Studies in Graph Theory, Mathematical Association of America, Vol. II, D.R. Fulkerson (Ed.), 1975, pp. 225-245. MAA Studies in Mathematics, Washington, D.C.
4. D. Karger, R. Motwani, and M. Sudan, “Approximate graph coloring by semidefinite programming,” in 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, 20-22 November 1994, pp. 2-13, IEEE, New York, 1994.
5. D.E. Knuth, “The sandwich theorem,” The Electronic Journal of Combinatorics 1 (1994), #A1.
6. L. Lovász, “On the shannon capacity of a graph,” IEEE Transactions on Information Theory IT-25 (1979), 1-7.
7. L. Lovász and A. Schrijver, “Cones of matrices and set functions and 0-1 optimization,” SIAM Journal on Optimization 1 (1991), 166-190.
8. R.J. McEliece, E.R. Rodemich, and H.C. Rumsey, Jr., “The Lovász bound and some generalizations,” J. Combinatorics, Inform. Syst. Sci. 3 (1978), 134-152.
9. A. Schrijver, “A comparison of the delsarte and Lovász bounds,” IEEE Transactions on Information Theory IT-25 (1979), 425-429.
1996. CBMS Lecture Notes.
2. M. Gr\ddot otschel, L. Lovász, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd edition, Section 9.3, Springer-Verlag, Berlin, 1993.
3. A.H. Hoffman, “Eigenvalues of graphs,” in Studies in Graph Theory, Mathematical Association of America, Vol. II, D.R. Fulkerson (Ed.), 1975, pp. 225-245. MAA Studies in Mathematics, Washington, D.C.
4. D. Karger, R. Motwani, and M. Sudan, “Approximate graph coloring by semidefinite programming,” in 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, 20-22 November 1994, pp. 2-13, IEEE, New York, 1994.
5. D.E. Knuth, “The sandwich theorem,” The Electronic Journal of Combinatorics 1 (1994), #A1.
6. L. Lovász, “On the shannon capacity of a graph,” IEEE Transactions on Information Theory IT-25 (1979), 1-7.
7. L. Lovász and A. Schrijver, “Cones of matrices and set functions and 0-1 optimization,” SIAM Journal on Optimization 1 (1991), 166-190.
8. R.J. McEliece, E.R. Rodemich, and H.C. Rumsey, Jr., “The Lovász bound and some generalizations,” J. Combinatorics, Inform. Syst. Sci. 3 (1978), 134-152.
9. A. Schrijver, “A comparison of the delsarte and Lovász bounds,” IEEE Transactions on Information Theory IT-25 (1979), 425-429.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition