Geodesic
Diameters and eigenvalues
Journal of the American Mathematical Society, Tome 02 (1989) no. 2, pp. 187-196

Voir la notice de l'article provenant de la source American Mathematical Society

We derive a new upper bound for the diameter of a $k$-regular graph $G$ as a function of the eigenvalues of the adjacency matrix. Namely, suppose the adjacency matrix of $G$ has eigenvalues ${\lambda _1},{\lambda _2}, \ldots ,{\lambda _n}$ with $\left | {{\lambda _1}} \right | \geq \left | {{\lambda _2}} \right | \geq \cdots \geq \left | {{\lambda _n}} \right |$ where ${\lambda _1} = k$, $\lambda = \left | {{\lambda _2}} \right |$. Then the diameter $D(G)$ must satisfy \[ D(G) \leq \left \lceil {\log (n - 1)/{\text {log}}(k/\lambda )} \right \rceil \]. We will consider families of graphs whose eigenvalues can be explicitly determined. These graphs are determined by sums or differences of vertex labels. Namely, the pair $\left \{ {i,j} \right \}$ being an edge depends only on the value $i + j$ (or $i - j$ for directed graphs). We will show that these graphs are expander graphs with small diameters by using an inequality on character sums, which was recently proved by N. M. Katz. 
Chung, F. R. K. Diameters and eigenvalues. Journal of the American Mathematical Society, Tome 02 (1989) no. 2, pp. 187-196. doi: 10.1090/S0894-0347-1989-0965008-X
@article{10_1090_S0894_0347_1989_0965008_X,
     author = {Chung, F. R. K.},
     title = {Diameters and eigenvalues},
     journal = {Journal of the American Mathematical Society},
     pages = {187--196},
     year = {1989},
     volume = {02},
     number = {2},
     doi = {10.1090/S0894-0347-1989-0965008-X},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-0965008-X/}
}
TY  - JOUR
AU  - Chung, F. R. K.
TI  - Diameters and eigenvalues
JO  - Journal of the American Mathematical Society
PY  - 1989
SP  - 187
EP  - 196
VL  - 02
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-0965008-X/
DO  - 10.1090/S0894-0347-1989-0965008-X
ID  - 10_1090_S0894_0347_1989_0965008_X
ER  - 
%0 Journal Article
%A Chung, F. R. K.
%T Diameters and eigenvalues
%J Journal of the American Mathematical Society
%D 1989
%P 187-196
%V 02
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-0965008-X/
%R 10.1090/S0894-0347-1989-0965008-X
%F 10_1090_S0894_0347_1989_0965008_X

[1] Ajtai, M., Komlós, J., Szemerédi, E. Sorting in 𝑐𝑙𝑜𝑔𝑛 parallel steps Combinatorica 1983 1 19

[2] Alon, N., Milman, V. D. 𝜆₁, isoperimetric inequalities for graphs, and superconcentrators J. Combin. Theory Ser. B 1985 73 88

[3] Alon, N. Eigenvalues and expanders Combinatorica 1986 83 96

[4] Alon, N., Galil, Z., Milman, V. D. Better expanders and superconcentrators J. Algorithms 1987 337 347

[5] Bassalygo, L. A. Asymptotically optimal switching circuits Problemy Peredachi Informatsii 1981 81 88

[6] Beck, József On size Ramsey number of paths, trees, and circuits. I J. Graph Theory 1983 115 129

[7] Benson, Clark T. Minimal regular graphs of girths eight and twelve Canadian J. Math. 1966 1091 1094

[8] Bondy, J. A., Simonovits, M. Cycles of even length in graphs J. Combinatorial Theory Ser. B 1974 97 105

[9] Bose, R. C., Chowla, S. Theorems in the additive theory of numbers Comment. Math. Helv. 1962/63 141 147

[10] Brown, W. G. On graphs that do not contain a Thomsen graph Canad. Math. Bull. 1966 281 285

[11] Buck, Marshall W. Expanders and diffusers SIAM J. Algebraic Discrete Methods 1986 282 304

[12] Chung, F. R. K. On concentrators, superconcentrators, generalizers, and nonblocking networks Bell System Tech. J. 1979 1765 1777

[13] Diaconis, Persi Group representations in probability and statistics 1988

[14] Faudree, R. J., Simonovits, M. On a class of degenerate extremal graph problems Combinatorica 1983 83 93

[15] Frankl, P., Wilson, R. M. Intersection theorems with geometric consequences Combinatorica 1981 357 368

[16] Friedman, J., Pippenger, N. Expanding graphs contain all small trees Combinatorica 1987 71 76

[17] Gabber, Ofer, Galil, Zvi Explicit constructions of linear-sized superconcentrators J. Comput. System Sci. 1981 407 420

[18] Ihara, Yasutaka Discrete subgroups of 𝑃𝐿(2,𝑘_{℘}) 1966 272 278

[19] Jimbo, S., Maruoka, A. Expanders obtained from affine transformations Combinatorica 1987 343 355

[20] Katz, Nicholas M. An estimate for character sums J. Amer. Math. Soc. 1989 197 200

[21] Lengauer, Thomas, Tarjan, Robert E. Asymptotically tight bounds on time-space trade-offs in a pebble game J. Assoc. Comput. Mach. 1982 1087 1130

[22] Lubotzky, A., Phillips, R., Sarnak, P. Ramanujan graphs Combinatorica 1988 261 277

[23] Margulis, G. A. Explicit constructions of expanders Problemy Peredači Informacii 1973 71 80

[24] Pippenger, Nicholas Superconcentrators SIAM J. Comput. 1977 298 304

[25] Paul, Wolfgang J., Tarjan, Robert Endre, Celoni, James R. Space bounds for a game on graphs Math. Systems Theory 1976/77 239 251

[26] Schmidt, Wolfgang M. Equations over finite fields. An elementary approach 1976

[27] Singleton, Robert On minimal graphs of maximum even girth J. Combinatorial Theory 1966 306 332

[28] Tanner, R. Michael Explicit concentrators from generalized 𝑁-gons SIAM J. Algebraic Discrete Methods 1984 287 293

[29] Tompa, Martin Time-space tradeoffs for computing functions, using connectivity properties of their circuits J. Comput. System Sci. 1980 118 132

[30] Valiant, Leslie G. Graph-theoretic properties in computational complexity J. Comput. System Sci. 1976 278 285

Cité par Sources :