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

[Enhancements On Off] (What's this?)

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

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