×

zbMATH — the first resource for mathematics

Diameters and eigenvalues. (English) Zbl 0678.05037
Let G be a regular graph of degree k, diameter D(G) and eigenvalues \(\lambda_ 1,\lambda_ 2,..\). where \(| \lambda_ 1| \geq | \lambda_ 2| \geq....\) If \(| \lambda_ 2| =\lambda\), then \(D(G)\leq \lceil \log (n-1)/\log (k/\lambda)\rceil.\) This result improves a previous bound by N. Alon and V. D. Milman \([\lambda_ 1\), isoperimetric inequalities for graphs and superconcentrators, J. Comb. Theory, Ser. B 38, 73-88 (1985; Zbl 0549.05051)]. Some expanders with small diameter are constructed, too.
Reviewer: D.Cvetković

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[2] N. Alon and V. D. Milman, \?\(_{1}\), isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73 – 88. · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9 · doi.org
[3] N. Alon, Eigenvalues and expanders, Combinatorica 6 (1986), no. 2, 83 – 96. Theory of computing (Singer Island, Fla., 1984). · Zbl 0661.05053 · doi:10.1007/BF02579166 · doi.org
[4] N. Alon, Z. Galil, and V. D. Milman, Better expanders and superconcentrators, J. Algorithms 8 (1987), no. 3, 337 – 347. · Zbl 0641.68102 · doi:10.1016/0196-6774(87)90014-9 · doi.org
[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; Russian transl., Problems Inform. Transmission 17 (1981), no. 3, 81 – 88. · Zbl 0486.94021
[7] József Beck, On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory 7 (1983), no. 1, 115 – 129. · Zbl 0508.05047 · doi:10.1002/jgt.3190070115 · doi.org
[8] Clark T. Benson, Minimal regular graphs of girths eight and twelve, Canad. J. Math. 18 (1966), 1091 – 1094. · Zbl 0146.45701 · doi:10.4153/CJM-1966-109-8 · doi.org
[9] J. A. Bondy and M. Simonovits, Cycles of even length in graphs, J. Combinatorial Theory Ser. B 16 (1974), 97 – 105. · Zbl 0283.05108
[10] R. C. Bose and S. Chowla, Theorems in the additive theory of numbers, Comment. Math. Helv. 37 (1962/1963), 141 – 147. · Zbl 0109.03301 · doi:10.1007/BF02566968 · doi.org
[11] W. G. Brown, On graphs that do not contain a Thomsen graph, Canad. Math. Bull. 9 (1966), 281 – 285. · Zbl 0178.27302 · doi:10.4153/CMB-1966-036-2 · doi.org
[12] Marshall W. Buck, Expanders and diffusers, SIAM J. Algebraic Discrete Methods 7 (1986), no. 2, 282 – 304. · Zbl 0612.68061 · doi:10.1137/0607032 · doi.org
[13] Ying Cheng, Diameters of double loop local computer networks, 1988, preprint. · Zbl 0648.05030
[14] F. R. K. Chung, On concentrators, superconcentrators, generalizers, and nonblocking networks, Bell System Tech. J. 58 (1979), no. 8, 1765 – 1777. · Zbl 0415.94021 · doi:10.1002/j.1538-7305.1979.tb02972.x · doi.org
[15] 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. · Zbl 0695.60012
[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. · Zbl 0144.23302
[18] R. J. Faudree and M. Simonovits, On a class of degenerate extremal graph problems, Combinatorica 3 (1983), no. 1, 83 – 93. · Zbl 0521.05037 · doi:10.1007/BF02579343 · doi.org
[19] P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357 – 368. · Zbl 0498.05048 · doi:10.1007/BF02579457 · doi.org
[20] J. Friedman and N. Pippenger, Expanding graphs contain all small trees, Combinatorica 7 (1987), no. 1, 71 – 76. · Zbl 0624.05028 · doi:10.1007/BF02579202 · doi.org
[21] 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. · Zbl 0487.05045 · doi:10.1016/0022-0000(81)90040-4 · doi.org
[22] Yasutaka Ihara, Discrete subgroups of \?\?(2,\?_℘), Algebraic Groups and Discontinuous Subgroups (Proc. Sympos. Pure Math., Boulder, Colo., 1965) Amer. Math. Soc., Providence, R.I., 1966, pp. 272 – 278.
[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, Combinatorica 7 (1987), no. 4, 343 – 355. · Zbl 0637.05017 · doi:10.1007/BF02579322 · doi.org
[25] Nicholas M. Katz, An estimate for character sums, J. Amer. Math. Soc. 2 (1989), no. 2, 197 – 200. · Zbl 0672.10026
[26] -, Factoring polynomials in finite fields: an application of Lang-Weil to a problem in graph theory, 1988, preprint.
[27] 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. · Zbl 0495.68037 · doi:10.1145/322344.322354 · doi.org
[28] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261 – 277. · Zbl 0661.05035 · doi:10.1007/BF02126799 · doi.org
[29] G. A. Margulis, Explicit constructions of expanders, Problemy Peredači Informacii 9 (1973), no. 4, 71 – 80 (Russian). · Zbl 0312.22011
[30] M. Pinsker, On the complexity of a concentrator, 7th Internat. Teletraffic Conf., Stockholm, June 1973, 318/1-318/4.
[31] Nicholas Pippenger, Superconcentrators, SIAM J. Comput. 6 (1977), no. 2, 298 – 304. · Zbl 0361.05035 · doi:10.1137/0206022 · doi.org
[32] -, Advances in pebbling, Internat. Colloq. on Automation Languages and Programming, Vol. 9, 1982, pp. 407-417.
[33] 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. , https://doi.org/10.1007/BF01683275 Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni, Correction to: ”Space bounds for a game on graphs”, Math. Systems Theory 11 (1977/78), no. 1, 85. · Zbl 0374.90099 · doi:10.1007/BF01768470 · doi.org
[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] Wolfgang M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin-New York, 1976. · Zbl 0329.12001
[37] Robert Singleton, On minimal graphs of maximum even girth, J. Combinatorial Theory 1 (1966), 306 – 332. · Zbl 0168.44703
[38] R. Michael Tanner, Explicit concentrators from generalized \?-gons, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 287 – 293. · Zbl 0554.05045 · doi:10.1137/0605030 · doi.org
[39] Martin Tompa, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, J. Comput. System Sci. 20 (1980), no. 2, 118 – 132. ACM-SIGACT Symposium on the Theory of Computing (San Diego, Calif., 1978). · Zbl 0435.68034 · doi:10.1016/0022-0000(80)90056-2 · doi.org
[40] Leslie G. Valiant, Graph-theoretic properties in computational complexity, J. Comput. System Sci. 13 (1976), no. 3, 278 – 285. Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N. M., 1975). · Zbl 0354.68071 · doi:10.1016/S0022-0000(76)80041-4 · doi.org
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.