no. 12 · Tuesday 10 November 2026
Diameter Bounds and Finiteness of Graphs from Local Intersection Data
Abstract
We extend the Bakry–Émery curvature framework on graphs, broadening its applications and strengthening the resulting diameter bounds. We study diameter bounds and finiteness for amply regular graphs, distance-regular graphs, $(s,c,a,k)$-graphs, and locally strongly regular graphs. In particular, for an amply regular graph with parameters $(v,k,λ,μ)$, we prove that \[{\rm{diam}}(G)\le4+8\log\frac{k}{\max\{λ,μ\}}\] when $μ>2$ and $k\ge3λ^2/μ$, improving the previous linear bound $4k/(λ+4)$ to a logarithmic bound. We also address several related conjectures. In their monograph \emph{Distance-Regular Graphs}, Brouwer, Cohen, and Neumaier conjectured that every amply regular graph with $μ>1$, except the icosahedron, satisfies ${\rm{diam}}(G)\le2k/(λ+2)$. We confirm this bound when $μ>λ+1$ and give counterexamples to the conjecture with $μ=λ$. For amply regular graphs with $μ\geλ$ and $μ>1$, we obtain ${\rm{diam}}(G)\le 2k/μ+1$. This proves the Qiao–Park–Koolen conjecture. In 1983, Terwilliger conjectured that every $(s,c,a,k)$-graph with $c>1$ is finite. We prove this conjecture when ``$s>2$, $c>2$, $(s,c)\ne(4,3)$'' and when ``$s=2$, $c>7$''. Moreover, we prove Weetman's finiteness conjecture for locally strongly regular graphs when the local parameter $μ>1$, and disprove his stronger conjecture that every strongly regular graph is an $\mathscr{S}$-graph. We also prove that every graph whose local graphs all have rank 3 is finite, which in particular proves a conjecture of Soicher in 1992.
- fields
- Combinatorics