## Diameters and eigenvalues

HTML articles powered by AMS MathViewer

- by F. R. K. Chung PDF
- J. Amer. Math. Soc.
**2**(1989), 187-196 Request permission

## Abstract:

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.## References

- M. Ajtai, J. Komlós, and E. Szemerédi,
*Sorting in $c\,\textrm {log}\,n$ parallel steps*, Combinatorica**3**(1983), no. 1, 1–19. MR**716418**, DOI 10.1007/BF02579338 - N. Alon and V. D. Milman,
*$\lambda _1,$ isoperimetric inequalities for graphs, and superconcentrators*, J. Combin. Theory Ser. B**38**(1985), no. 1, 73–88. MR**782626**, DOI 10.1016/0095-8956(85)90092-9 - N. Alon,
*Eigenvalues and expanders*, Combinatorica**6**(1986), no. 2, 83–96. Theory of computing (Singer Island, Fla., 1984). MR**875835**, DOI 10.1007/BF02579166 - N. Alon, Z. Galil, and V. D. Milman,
*Better expanders and superconcentrators*, J. Algorithms**8**(1987), no. 3, 337–347. MR**905991**, DOI 10.1016/0196-6774(87)90014-9
W. N. Anderson, Jr. and T. D. Morley, - L. A. Bassalygo,
*Asymptotically optimal switching circuits*, Problemy Peredachi Informatsii**17**(1981), no. 3, 81–88 (Russian); English transl., Problems Inform. Transmission**17**(1981), no. 3, 206–211. MR**673739** - József Beck,
*On size Ramsey number of paths, trees, and circuits. I*, J. Graph Theory**7**(1983), no. 1, 115–129. MR**693028**, DOI 10.1002/jgt.3190070115 - Clark T. Benson,
*Minimal regular graphs of girths eight and twelve*, Canadian J. Math.**18**(1966), 1091–1094. MR**197342**, DOI 10.4153/CJM-1966-109-8 - J. A. Bondy and M. Simonovits,
*Cycles of even length in graphs*, J. Combinatorial Theory Ser. B**16**(1974), 97–105. MR**340095**, DOI 10.1016/0095-8956(74)90052-5 - R. C. Bose and S. Chowla,
*Theorems in the additive theory of numbers*, Comment. Math. Helv.**37**(1962/63), 141–147. MR**144877**, DOI 10.1007/BF02566968 - W. G. Brown,
*On graphs that do not contain a Thomsen graph*, Canad. Math. Bull.**9**(1966), 281–285. MR**200182**, DOI 10.4153/CMB-1966-036-2 - Marshall W. Buck,
*Expanders and diffusers*, SIAM J. Algebraic Discrete Methods**7**(1986), no. 2, 282–304. MR**830648**, DOI 10.1137/0607032
Ying Cheng, - F. R. K. Chung,
*On concentrators, superconcentrators, generalizers, and nonblocking networks*, Bell System Tech. J.**58**(1979), no. 8, 1765–1777. MR**546309**, DOI 10.1002/j.1538-7305.1979.tb02972.x - Persi Diaconis,
*Group representations in probability and statistics*, Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988. MR**964069**
M. Eichler, - R. J. Faudree and M. Simonovits,
*On a class of degenerate extremal graph problems*, Combinatorica**3**(1983), no. 1, 83–93. MR**716423**, DOI 10.1007/BF02579343 - P. Frankl and R. M. Wilson,
*Intersection theorems with geometric consequences*, Combinatorica**1**(1981), no. 4, 357–368. MR**647986**, DOI 10.1007/BF02579457 - J. Friedman and N. Pippenger,
*Expanding graphs contain all small trees*, Combinatorica**7**(1987), no. 1, 71–76. MR**905153**, DOI 10.1007/BF02579202 - Ofer Gabber and Zvi Galil,
*Explicit constructions of linear-sized superconcentrators*, J. Comput. System Sci.**22**(1981), no. 3, 407–420. Special issued dedicated to Michael Machtey. MR**633542**, DOI 10.1016/0022-0000(81)90040-4 - Yasutaka Ihara,
*Discrete subgroups of $\textrm {PL}(2,\,k_{\wp })$*, Algebraic Groups and Discontinuous Subgroups (Proc. Sympos. Pure Math., Boulder, Colo., 1965) Amer. Math. Soc., Providence, R.I., 1966, pp. 272–278. MR**0205952**
J. JáJa, - S. Jimbo and A. Maruoka,
*Expanders obtained from affine transformations*, Combinatorica**7**(1987), no. 4, 343–355. MR**931192**, DOI 10.1007/BF02579322 - Nicholas M. Katz,
*An estimate for character sums*, J. Amer. Math. Soc.**2**(1989), no. 2, 197–200. MR**965007**, DOI 10.1090/S0894-0347-1989-0965007-8
—, - Thomas Lengauer and Robert E. Tarjan,
*Asymptotically tight bounds on time-space trade-offs in a pebble game*, J. Assoc. Comput. Mach.**29**(1982), no. 4, 1087–1130. MR**674259**, DOI 10.1145/322344.322354 - A. Lubotzky, R. Phillips, and P. Sarnak,
*Ramanujan graphs*, Combinatorica**8**(1988), no. 3, 261–277. MR**963118**, DOI 10.1007/BF02126799 - G. A. Margulis,
*Explicit constructions of expanders*, Problemy Peredači Informacii**9**(1973), no. 4, 71–80 (Russian). MR**0484767**
M. Pinsker, - Nicholas Pippenger,
*Superconcentrators*, SIAM J. Comput.**6**(1977), no. 2, 298–304. MR**446750**, DOI 10.1137/0206022
—, - Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni,
*Space bounds for a game on graphs*, Math. Systems Theory**10**(1976/77), no. 3, 239–251. MR**451347**, DOI 10.1007/BF01683275
C. S. Raghavendra and J. A. Silvester, - Wolfgang M. Schmidt,
*Equations over finite fields. An elementary approach*, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin-New York, 1976. MR**0429733** - Robert Singleton,
*On minimal graphs of maximum even girth*, J. Combinatorial Theory**1**(1966), 306–332. MR**201347** - R. Michael Tanner,
*Explicit concentrators from generalized $N$-gons*, SIAM J. Algebraic Discrete Methods**5**(1984), no. 3, 287–293. MR**752035**, DOI 10.1137/0605030 - Martin Tompa,
*Time-space tradeoffs for computing functions, using connectivity properties of their circuits*, J. Comput. System Sci.**20**(1980), no. 2, 118–132. MR**574588**, DOI 10.1016/0022-0000(80)90056-2 - Leslie G. Valiant,
*Graph-theoretic properties in computational complexity*, J. Comput. System Sci.**13**(1976), no. 3, 278–285. MR**441008**, DOI 10.1016/S0022-0000(76)80041-4

*Eigenvalues of the Laplacian of a graph*, Univ. Maryland Technical Report TR-71-45, 1971.

*Diameters of double loop local computer networks*, 1988, preprint.

*Quaternary quadratic forms and the Riemann hypothesis for congruence zeta functions*, Arch. Math.

**5**(1954), 355-366. P. Erdös, A. Rényi, and V. T. Sós,

*On a problem of graph theory*, Studia Sci. Math. Hungar.

**1**(1966), 215-235.

*Time space tradeoffs for some algebraic problems*, Proc. 12th Annual ACM Sympos. on Theory of Computing, 1980, AMC, NY, 1980, pp. 339-350.

*Factoring polynomials in finite fields: an application of Lang-Weil to a problem in graph theory*, 1988, preprint.

*On the complexity of a concentrator*, 7th Internat. Teletraffic Conf., Stockholm, June 1973, 318/1-318/4.

*Advances in pebbling*, Internat. Colloq. on Automation Languages and Programming, Vol. 9, 1982, pp. 407-417.

*A survey of multi-connected loop topologies for local computer networks*, Computer Networks and ISDN Systems

**2**(1986), 29-42. S. Ramanujan,

*On certain arithmetical functions*, Trans. Cambridge Philos. Soc.

**22**(9) (1916), 159-184.

## Additional Information

- © Copyright 1989 American Mathematical Society
- Journal: J. Amer. Math. Soc.
**2**(1989), 187-196 - MSC: Primary 05C50; Secondary 05C38
- DOI: https://doi.org/10.1090/S0894-0347-1989-0965008-X
- MathSciNet review: 965008