Diameters and eigenvalues

Journal of the American Mathematical Society - Tập 2 Số 2 - Trang 187-196
Fan Chung

Tóm tắt

We derive a new upper bound for the diameter of a k k -regular graph G G as a function of the eigenvalues of the adjacency matrix. Namely, suppose the adjacency matrix of G G has eigenvalues λ 1 , λ 2 , … , λ n {\lambda _1},{\lambda _2}, \ldots ,{\lambda _n} with | λ 1 | ≥ | λ 2 | ≥ ⋯ ≥ | λ n | \left | {{\lambda _1}} \right | \geq \left | {{\lambda _2}} \right | \geq \cdots \geq \left | {{\lambda _n}} \right | where λ 1 = k {\lambda _1} = k , λ = | λ 2 | \lambda = \left | {{\lambda _2}} \right | . Then the diameter D ( G ) D(G) must satisfy \[ D ( G ) ≤ ⌈ log ⁡ ( n − 1 ) / log ( k / λ ) ⌉ 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 { i , j } \left \{ {i,j} \right \} being an edge depends only on the value i + j i + j (or i − j 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.

Từ khóa


Tài liệu tham khảo

Ajtai, M., 1983, Sorting in 𝑐𝑙𝑜𝑔𝑛 parallel steps, Combinatorica, 3, 1, 10.1007/BF02579338

Alon, N., 1985, 𝜆₁, isoperimetric inequalities for graphs, and superconcentrators, J. Combin. Theory Ser. B, 38, 73, 10.1016/0095-8956(85)90092-9

Alon, N., 1986, Eigenvalues and expanders, Combinatorica, 6, 83, 10.1007/BF02579166

Alon, N., 1987, Better expanders and superconcentrators, J. Algorithms, 8, 337, 10.1016/0196-6774(87)90014-9

W. N. Anderson, Jr. and T. D. Morley, Eigenvalues of the Laplacian of a graph, Univ. Maryland Technical Report TR-71-45, 1971.

Bassalygo, L. A., Asymptotically optimal switching circuits

Beck, József, 1983, On size Ramsey number of paths, trees, and circuits. I, J. Graph Theory, 7, 115, 10.1002/jgt.3190070115

Benson, Clark T., 1966, Minimal regular graphs of girths eight and twelve, Canadian J. Math., 18, 1091, 10.4153/CJM-1966-109-8

Bondy, J. A., 1974, Cycles of even length in graphs, J. Combinatorial Theory Ser. B, 16, 97, 10.1016/0095-8956(74)90052-5

Bose, R. C., 1962, Theorems in the additive theory of numbers, Comment. Math. Helv., 37, 141, 10.1007/BF02566968

Brown, W. G., 1966, On graphs that do not contain a Thomsen graph, Canad. Math. Bull., 9, 281, 10.4153/CMB-1966-036-2

Buck, Marshall W., 1986, Expanders and diffusers, SIAM J. Algebraic Discrete Methods, 7, 282, 10.1137/0607032

Ying Cheng, Diameters of double loop local computer networks, 1988, preprint.

Chung, F. R. K., 1979, On concentrators, superconcentrators, generalizers, and nonblocking networks, Bell System Tech. J., 58, 1765, 10.1002/j.1538-7305.1979.tb02972.x

Diaconis, Persi, 1988, Group representations in probability and statistics, 11, 10.1007/BFb0086177

M. Eichler, 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.

Faudree, R. J., 1983, On a class of degenerate extremal graph problems, Combinatorica, 3, 83, 10.1007/BF02579343

Frankl, P., 1981, Intersection theorems with geometric consequences, Combinatorica, 1, 357, 10.1007/BF02579457

Friedman, J., 1987, Expanding graphs contain all small trees, Combinatorica, 7, 71, 10.1007/BF02579202

Gabber, Ofer, 1981, Explicit constructions of linear-sized superconcentrators, J. Comput. System Sci., 22, 407, 10.1016/0022-0000(81)90040-4

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

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.

Jimbo, S., 1987, Expanders obtained from affine transformations, Combinatorica, 7, 343, 10.1007/BF02579322

Katz, Nicholas M., 1989, An estimate for character sums, J. Amer. Math. Soc., 2, 197, 10.2307/1990974

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

Lengauer, Thomas, 1982, Asymptotically tight bounds on time-space trade-offs in a pebble game, J. Assoc. Comput. Mach., 29, 1087, 10.1145/322344.322354

Lubotzky, A., 1988, Ramanujan graphs, Combinatorica, 8, 261, 10.1007/BF02126799

Margulis, G. A., 1973, Explicit constructions of expanders, Problemy Pereda\v{c}i Informacii, 9, 71

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

Pippenger, Nicholas, 1977, Superconcentrators, SIAM J. Comput., 6, 298, 10.1137/0206022

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

Paul, Wolfgang J., 1976, Space bounds for a game on graphs, Math. Systems Theory, 10, 239, 10.1007/BF01683275

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.

S. Ramanujan, On certain arithmetical functions, Trans. Cambridge Philos. Soc. 22 (9) (1916), 159-184.

Schmidt, Wolfgang M., 1976, Equations over finite fields. An elementary approach, 10.1007/BFb0080437

Singleton, Robert, 1966, On minimal graphs of maximum even girth, J. Combinatorial Theory, 1, 306, 10.1016/S0021-9800(66)80054-6

Tanner, R. Michael, 1984, Explicit concentrators from generalized 𝑁-gons, SIAM J. Algebraic Discrete Methods, 5, 287, 10.1137/0605030

Tompa, Martin, 1980, Time-space tradeoffs for computing functions, using connectivity properties of their circuits, J. Comput. System Sci., 20, 118, 10.1016/0022-0000(80)90056-2

Valiant, Leslie G., 1976, Graph-theoretic properties in computational complexity, J. Comput. System Sci., 13, 278, 10.1016/S0022-0000(76)80041-4

Thông tin
Thông tin xuất bản

Journal of the American Mathematical Society

Tập 2 Số 2

187-196

Thông tin tác giả