Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

Diameters and eigenvalues


Author: F. R. K. Chung
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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\vert {{\lambda _1}} \right\vert \geq \left\vert {{\lambda _2}} \right\vert \geq \cdots \geq \left\vert {{\lambda _n}} \right\vert$ where $ {\lambda _1} = k$, $ \lambda = \left\vert {{\lambda _2}} \right\vert$. Then the diameter $ D(G)$ must satisfy

$\displaystyle 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 [Enhancements On Off] (What's this?)

  • [1] M. Ajtai, J. Komlós, and E. Szemerédi, Sorting in $ c\log n$ parallel steps, Combinatorica 3 (1983), 1-19. MR 716418 (85d:68017)
  • [2] N. Alon and V. D. Milman, $ {\lambda _1}$, isoperimetric inequalities for graphs and superconcentrators, J. Combin. Theory Ser. B 38 (1985), 73-88. MR 782626 (87b:05092)
  • [3] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1983), 83-96. MR 875835 (88e:05077)
  • [4] N. Alon, Z. Galil, and V. D. Milman, Better expanders and superconcentrators, J. Algorithms 8 (1987), 337-347. MR 905991 (89f:68023)
  • [5] W. N. Anderson, Jr. and T. D. Morley, Eigenvalues of the Laplacian of a graph, Univ. Maryland Technical Report TR-71-45, 1971.
  • [6] L. A. Bassalygo, Asymptotically optimal switching circuits, Problems Inform. Transmission 17 (1981), 206-211. MR 673739 (83j:94031)
  • [7] J. Beck, On size Ramsey number of paths, trees and circuits. I, J. Graph Theory 7 (1983), 115-129. MR 693028 (84g:05102)
  • [8] C. T. Benson, Minimal regular graphs of girths eight and twelve, Canad. J. Math. 8 (1966), 1091-1094. MR 0197342 (33:5507)
  • [9] J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combin. Theory Ser. B 16 (1974), 97-105. MR 0340095 (49:4851)
  • [10] R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962), 141-147. MR 0144877 (26:2418)
  • [11] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281-285. MR 0200182 (34:81)
  • [12] M. W. Buck, Expanders and diffusers, SIAM J. Algebraic Discrete Methods 7 (1986), 282-304. MR 830648 (87e:68088)
  • [13] Ying Cheng, Diameters of double loop local computer networks, 1988, preprint.
  • [14] F. R. K. Chung, On concentrators, superconcentrators, generalizers and nonblocking networks, Bell Systems Tech. J. 58 (1978), 1765-1777. MR 546309 (80k:94059)
  • [15] P. Diaconis, Group representation in probability and statistics, 1988, preprint. MR 964069 (90a:60001)
  • [16] M. Eichler, Quaternary quadratic forms and the Riemann hypothesis for congruence zeta functions, Arch. Math. 5 (1954), 355-366.
  • [17] 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.
  • [18] R. J. Faudree and M. Simonovits, On a class of degenerate extremal graph problem, Combinatorica 3 (1983), 97-107. MR 716423 (85d:05143)
  • [19] P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357-368. MR 647986 (84g:05085)
  • [20] J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), 71-76. MR 905153 (88k:05063)
  • [21] O. Gabber and Z. Galil, Explicit construction of linear sized superconcentrators, J. Comput. System Sci. 22 (1981), 407-420. MR 633542 (83d:94029)
  • [22] Y. Ihara, Discrete subgroups of $ PL(2,{k_p})$, Proc. Sympos. Pure Math., Vol. 9, Amer. Math. Soc., Providence, R. I., 1968, pp. 272-278. MR 0205952 (34:5777)
  • [23] J. JáJa, Time space tradeoffs for some algebraic problems, Proc. 12th Annual ACM Sympos. on Theory of Computing, 1980, AMC, NY, 1980, pp. 339-350.
  • [24] S. Jimbo and A. Maruoka, Expanders obtained from affine transformations (extended abstract), 1984, preprint. MR 931192 (89d:68071)
  • [25] N. M. Katz, An estimate for character sums, J. Amer. Math. Soc. 2 (1989), 197-200. MR 965007 (90b:11081)
  • [26] -, Factoring polynomials in finite fields: an application of Lang-Weil to a problem in graph theory, 1988, preprint.
  • [27] T. Lengauer and R. E. Tarjan, Asymptotically tight bounds on time space tradeoffs in a pebble game, J. Assoc. Comput. Mach. 29 (1982), 1087-1130. MR 674259 (83m:68080)
  • [28] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), 261-278. MR 963118 (89m:05099)
  • [29] G. A. Margulis, Explicit constructions of concentrators, Problemy Peredači Informacii 9 (1973), 71-80 (English transl. in Problems Inform. Transmission 9 (1975), 325-332). MR 0484767 (58:4643)
  • [30] M. Pinsker, On the complexity of a concentrator, 7th Internat. Teletraffic Conf., Stockholm, June 1973, 318/1-318/4.
  • [31] N. Pippenger, Superconcentrators, SIAM J. Comput. 6 (1977), 298-304. MR 0446750 (56:5074)
  • [32] -, Advances in pebbling, Internat. Colloq. on Automation Languages and Programming, Vol. 9, 1982, pp. 407-417.
  • [33] W. J. Paul, R. E. Tarjan, and J. R. Celoni, Space bounds for a game on graphs, Math. Soc. Theory 10 (1977), 239-251. MR 451347 (81h:68030a)
  • [34] C. S. Raghavendra and J. A. Silvester, A survey of multi-connected loop topologies for local computer networks, Computer Networks and ISDN Systems 2 (1986), 29-42.
  • [35] S. Ramanujan, On certain arithmetical functions, Trans. Cambridge Philos. Soc. 22 (9) (1916), 159-184.
  • [36] W. M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Math., Vol. 536, Springer-Verlag, Berlin and New York, 1976. MR 0429733 (55:2744)
  • [37] R. R. Singleton, On minimal graphs of maximum even girth, J. Combin. Theory 1 (1966), 306-332. MR 0201347 (34:1231)
  • [38] R. M. Tanner, Explicit construction of concentrators from generalized $ N$-gons, SIAM J. Algebraic Discrete Methods 5 (1984), 287-294. MR 752035 (85k:68080)
  • [39] M. Tompa, Time space tradeons for computing using connectivity properties of the circuits, J. Comput. System Sci. 20 (1980), 118-132. MR 574588 (81h:68032)
  • [40] L. G. Valiant, Graph theoretic properties in computational complexity, J. Comput. System Sci. 13 (1976), 278-285. MR 0441008 (55:13874)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 05C50, 05C38

Retrieve articles in all journals with MSC: 05C50, 05C38


Additional Information

DOI: https://doi.org/10.1090/S0894-0347-1989-0965008-X
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society