An asymptotically tight bound on oriented diameter

Abstract

Let $f(d)$ be the smallest integer such that every finite connected bridgeless simple graph of diameter $d$ admits a strong orientation of diameter at most $f(d)$. Chvátal and Thomassen (1978) proved $\lceil d^2/2\rceil +d\le f(d)\le 2d^2+2d$. In this paper, we prove that $\lceil d^2/2\rceil +d\le f(d)\le \lceil d^2/2\rceil +d+18$ for every $d\ge 2$, which shows that $f(d)=\lceil d^2/2\rceil +d+O(1)$ and determines both the quadratic and linear terms up to a bounded additive error. The key method of our proof is to construct a central subgraph $H$ that admits a strong orientation of diameter $O(d)$ and is within distance $\lfloor d/2\rfloor$ of every vertex outside it. We obtain the sharp linear coefficient by jointly estimating outside paths and their connecting paths in $H$ at the actual attachment vertices, rebuilding $H$ when necessary.

arXiv comment28 pages