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. 
@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},
     publisher = {mathdoc},
     volume = {02},
     number = {2},
     year = {1989},
     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
PB  - mathdoc
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
%I mathdoc
%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
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

[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 :