Open Research Index

The asymptotic maximum oriented diameter of graphs

Jiangdong Ai, Yaokun Feng, Hui Lei, Zijian Ren

arXivarxiv/2610.04660Oct 3, 2026math.COscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

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