Geodesic
Bounds on special subsets in graphs, eigenvalues and association schemes
Journal of Algebraic Combinatorics, Tome 7 (1998) no. 3, pp. 321-332.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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 $\mu $common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.
Keywords: eigenvalue of graph, association scheme 
@article{JAC_1998__7_3_a0,
     author = {van Dam, Edwin R.},
     title = {Bounds on special subsets in graphs, eigenvalues and association schemes},
     journal = {Journal of Algebraic Combinatorics},
     pages = {321--332},
     publisher = {mathdoc},
     volume = {7},
     number = {3},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a0/}
}
TY  - JOUR
AU  - van Dam, Edwin R.
TI  - Bounds on special subsets in graphs, eigenvalues and association schemes
JO  - Journal of Algebraic Combinatorics
PY  - 1998
SP  - 321
EP  - 332
VL  - 7
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a0/
LA  - en
ID  - JAC_1998__7_3_a0
ER  - 
%0 Journal Article
%A van Dam, Edwin R.
%T Bounds on special subsets in graphs, eigenvalues and association schemes
%J Journal of Algebraic Combinatorics
%D 1998
%P 321-332
%V 7
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a0/
%G en
%F JAC_1998__7_3_a0
van Dam, Edwin R. Bounds on special subsets in graphs, eigenvalues and association schemes. Journal of Algebraic Combinatorics, Tome 7 (1998) no. 3, pp. 321-332. http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a0/