{"id":"arxiv/2610.04660","url":"https://arxiv.org/abs/2610.04660","tags":["math.CO"],"score":0,"title":"The asymptotic maximum oriented diameter of graphs","domain":"math.CO","source":"arxiv","authors":["Jiangdong Ai","Yaokun Feng","Hui Lei","Zijian Ren"],"reviews":0,"subject":"math.CO","summary":"The oriented diameter of a connected bridgeless graph is the minimum diameter of a strong orientation. Let $f(d)$ be the maximum oriented diameter among all such graphs of diameter $d$. In 1978, Chvátal and Thomassen proved $f(d)\\le2d^2+2d$ and constructed graphs showing that any quadratic upper bound on $f(d)$ must have leading coefficient at least $1/2$. We prove that $f(d)\\le \\tfrac12d^2+7d$ for every integer $d\\ge1$. This matches the leading coefficient of their lower bound and establishes $f(d)=\\tfrac12d^2+O(d)$, determining the optimal quadratic coefficient. Our proof gives a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-03","reactions":{}}