{"id":"arxiv/2610.09648","url":"https://arxiv.org/abs/2610.09648","tags":["math.CO"],"score":0,"title":"An asymptotically tight bound on oriented diameter","domain":"math.CO","source":"arxiv","authors":["Jiangdong Ai","Yaojun Chen","Yaokun Feng","Hui Lei","Jifu Lin","Zijian Ren","Xiaolin Wang","Ruilin Zheng"],"reviews":0,"subject":"math.CO","summary":"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)$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}