Asymptotically attaining the Moore bound

Abstract

For positive integers $d$ and $k$, let $n_k(d)$ be the maximum order of a graph of maximum degree at most $d$ and diameter at most $k$. We prove that $$\underset{d\to \infty }{\lim }\frac{n_k(d)}{d^k}=1$$ for every fixed $k$, thereby resolving the asymptotic degree-diameter problem for fixed diameter and proving a conjecture of Bollobás. The lower bound comes from regular graphs $H_{k,q}$, indexed by prime powers $q$, whose vertices are partial flags in ${\mathbb{F}}_q^{2k+1}$. These graphs have diameter $k$ and order $|V(H_{k,q})|=(1+o(1))\Delta (H_{k,q}{)}^k$. We also construct, for every fixed $\ell \ge 2$, graphs of maximum degree at most $d$ and line-graph diameter at most $\ell$ with $(1+o(1))d^{\ell }$ edges.

$7+\epsilon$ pages