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.

References [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