Answers are grounded in this paper and cite their sources.
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 λ ₁,λ ₂, … ,λ ₙ with | λ ₁ | ≥ | λ ₂ | ≥ ⋯ ≥ | λ ₙ | where λ ₁ = k, λ = | λ ₂ |. Then the diameter $D(G)$ must satisfy \[ D(G) ≤ {log (n - 1)/{log}(k/λ )} \]. 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 \ i,j \ 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.
No takes yet. Share an insight, caveat, or question.
Fan Chung (1989) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: