{"id":"arxiv/2610.05061","url":"https://arxiv.org/abs/2610.05061","tags":["math.CO"],"score":0,"title":"An asymptotically tight bound on oriented diameter","domain":"math.CO","source":"arxiv","authors":["Yaojun Chen","Jifu Lin","Xiaolin Wang","Ruilin Zheng"],"reviews":0,"subject":"math.CO","summary":"Let $f(d)$ be the smallest integer such that every connected bridgeless graph of diameter $d$ admits an orientation with directed diameter at most $f(d)$. Chvátal and Thomassen (1978) proved $\\left\\lceil{d^2}/{2}\\right\\rceil+d\\le f(d) \\le 2d^2+2d$. In this paper, we prove that $f(d)\\le \\left\\lceil d^2/2\\right\\rceil+6d$, which shows $f(d)= d^2/2+Θ(d)$ and determine the leading quadratic coefficient of $f(d)$. The key method of our proof is to construct a central subgraph $H$ such that it admits a strong orientation of diameter $O(d)$ and the distance between $H$ and every vertex outside $H$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{}}