Diameters and eigenvalues

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.