Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes
Edwin R. van Dam
Tilburg University Department of Econometrics P.O. Box 90153 5000 LE Tilburg The Netherlands
DOI: 10.1023/A:1008675307444
Abstract
We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have μ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.
Pages: 321–332
Keywords: eigenvalue of graph; association scheme
Full Text: PDF
References
1. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Ergebnisse der Mathematik 3.18, Springer, Heidelberg, 1989.
2. F. Chatelin, Valeurs Propres de Matrices, Masson, Paris, 1988.
3. F.R.K. Chung, V. Faber, and T.A. Manteuffel, “An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian,” SIAM J. Discrete Math. 7 (1994), 443-457.
4. E.R. van Dam, “Regular graphs with four eigenvalues,” Linear Algebra Appl. 226-228 (1995), 139-162.
5. E.R. van Dam, “Three-class association schemes,” J. Alg. Combin. (to appear).
6. E.R. van Dam and W.H. Haemers, “Eigenvalues and the diameter of graphs,” Linear Multilin. Alg. 39 (1995), 33-44.
7. E.R. van Dam and W.H. Haemers, “Graphs with constant μand \? μ,” Discrete Math. 182 (1998), 293-307.
8. E.R. van Dam and W.H. Haemers, “A characterization of distance-regular graphs with diameter three,” J. Alg. Combin. 6 (1997), 299-303.
9. E.R. van Dam and E. Spence, “Small regular graphs with four eigenvalues,” Discrete Math. (to appear).
10. M.A. Fiol, E. Garriga, and J.L.A. Yebra, “On a class of polynomials and its relation with the spectra and diameters of graphs,” J. Comb. Theory (B) 67 (1996), 48-61.
11. W.H. Haemers, “Interlacing eigenvalues and graphs,” Linear Algebra Appl. 226-228 (1995), 593-616.
12. C. Helmberg, B. Mohar, S. Poljak, and F. Rendl, “A spectral approach to bandwidth and separator problems in graphs,” Linear Multilin. Alg. 39 (1995), 73-90.
13. T.J. Rivlin, Chebyshev Polynomials (2nd edition.), Wiley, New York, 1990.
2. F. Chatelin, Valeurs Propres de Matrices, Masson, Paris, 1988.
3. F.R.K. Chung, V. Faber, and T.A. Manteuffel, “An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian,” SIAM J. Discrete Math. 7 (1994), 443-457.
4. E.R. van Dam, “Regular graphs with four eigenvalues,” Linear Algebra Appl. 226-228 (1995), 139-162.
5. E.R. van Dam, “Three-class association schemes,” J. Alg. Combin. (to appear).
6. E.R. van Dam and W.H. Haemers, “Eigenvalues and the diameter of graphs,” Linear Multilin. Alg. 39 (1995), 33-44.
7. E.R. van Dam and W.H. Haemers, “Graphs with constant μand \? μ,” Discrete Math. 182 (1998), 293-307.
8. E.R. van Dam and W.H. Haemers, “A characterization of distance-regular graphs with diameter three,” J. Alg. Combin. 6 (1997), 299-303.
9. E.R. van Dam and E. Spence, “Small regular graphs with four eigenvalues,” Discrete Math. (to appear).
10. M.A. Fiol, E. Garriga, and J.L.A. Yebra, “On a class of polynomials and its relation with the spectra and diameters of graphs,” J. Comb. Theory (B) 67 (1996), 48-61.
11. W.H. Haemers, “Interlacing eigenvalues and graphs,” Linear Algebra Appl. 226-228 (1995), 593-616.
12. C. Helmberg, B. Mohar, S. Poljak, and F. Rendl, “A spectral approach to bandwidth and separator problems in graphs,” Linear Multilin. Alg. 39 (1995), 73-90.
13. T.J. Rivlin, Chebyshev Polynomials (2nd edition.), Wiley, New York, 1990.