Diameters and eigenvalues

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\vert {{\lambda _1}} \right\vert \geq \left\vert {{\lambda _2}} \right\vert \geq \cdots \geq \left\vert {{\lambda _n}} \right\vert$ where ${\lambda _1} = k$, $\lambda = \left\vert {{\lambda _2}} \right\vert$. 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.