Distance-Uniform Graphs with Large Diameter

Abstract

An $\epsilon$-distance-uniform graph is one in which from every vertex, all but an $\epsilon$-fraction of the remaining vertices are at some fixed distance $d$, called the critical distance. We consider the maximum possible value of $d$ in an $\epsilon$-distance-uniform graph with $n$ vertices. We show that for $\frac{1}{n}\le \epsilon \le \frac{1}{\log n}$, there exist $\epsilon$-distance-uniform graphs with critical distance $2^{\Omega (\frac{\log n}{\log {\epsilon }^{-1}})}$, disproving a conjecture of Alon et al. that $d$ can be at most logarithmic in $n$. We also show that our construction is best possible, in the sense that an upper bound on $d$ of the form $2^{O(\frac{\log n}{\log {\epsilon }^{-1}})}$ holds for all $\epsilon$ and $n$.

arXiv comment12 pages, 1 figure