An asymptotically tight bound on oriented diameter

Jiangdong Ai, Yaojun Chen, Yaokun Feng, Hui Lei, Jifu Lin, Zijian Ren, Xiaolin Wang, Ruilin Zheng

arXivarxiv/2610.09648Oct 7, 2026math.COscore 0

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)$…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.09648
curl -X POST /api/v1/records/arxiv/2610.09648/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.09648/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'