TOPICS
Search

Oriented Diameter

The oriented diameter of a connected graph without graph bridges is the minimum graph diameter among its graph orientations that are strongly connected. A strongly connected digraph has a directed graph path from every vertex to every other vertex. Such graph orientations exist by Robbins' theorem.

Let f(d) be the largest oriented diameter among connected graphs without graph bridges and with graph diameter d. Chen et al. (2026) proved

[d^2/2]+d<=f(d)<=[d^2/2]+6d,

where [x] is the ceiling function and the lower bound was previously known. Independently, Ai et al. (2026b) obtained f(d)<=d^2/2+7d. Thus f(d)=d^2/2+Theta(d). Chen et al. (2026) describe ChatGPT assistance that suggested the preliminary core-subgraph approach, while attributing the final coefficient improvement to their subsequent argument.

The two teams subsequently obtained the joint bound (Ai et al. 2026a)

[d^2/2]+d<=f(d)<=[d^2/2]+d+18.

Thus the additive error beyond the lower bound is at most 18.

See also

Graph Diameter, Graph Orientation, Robbins' Theorem

Explore with Wolfram|Alpha

References

Ai, J.; Chen, Y.; Feng, Y.; Lei, H.; Lin, J.; Ren, Z.; Wang, X.; and Zheng, R. "An Asymptotically Tight Bound on Oriented Diameter." 7 Oct 2026a. https://arxiv.org/abs/2610.09648.Ai, J.; Feng, Y.; Lei, H.; and Ren, Z. "The Asymptotic Maximum Oriented Diameter of Graphs." 3 Oct 2026b. https://arxiv.org/abs/2610.04660.Chen, Y.; Lin, J.; Wang, X.; and Zheng, R. "An Asymptotically Tight Bound on Oriented Diameter." 4 Oct 2026. https://arxiv.org/abs/2610.05061.

Cite this as:

Weisstein, Eric W. "Oriented Diameter." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/OrientedDiameter.html

Subject classifications