Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper establishes an asymptotically tight bound for the oriented diameter of graphs with a given diameter $d$, proving $f(d) \le \lceil d^2/2\rceil+d+18$, significantly improving the previous upper bound of $2d^2+2d$. The core technique involves constructing a central subgraph $H$ with a small oriented diameter and proximity to all other vertices, which is then refined by carefully estimating path lengths and rebuilding $H$ as needed. This result precisely determines the quadratic and linear terms of the oriented diameter bound, leaving only a small constant additive error.
The oriented diameter of a graph with diameter $d$ is now known to be at most $\lceil d^2/2\rceil+d+18$, a near-constant additive improvement on the established lower bound.
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)\le2d^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\ge2$, 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.