Diameters and Eigenvalues
Fan Chung · Journal of the American Mathematical Society · 1989
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.
Cited by 265 works. doi:10.1090/s0894-0347-1989-0965008-x Open-access PDF
Authors
References
- Eigenvalues and expanders
- Group representations in probability and statistics
- Superconcentrators
- Ramanujan graphs
- Explicit constructions of linear-sized superconcentrators
- λ1, Isoperimetric inequalities for graphs, and superconcentrators
- Sorting inc logn parallel steps
- Graph-theoretic properties in computational complexity
- Space bounds for a game on graphs
- Equations over Finite Fields An Elementary Approach