Bau–Dankelmann oriented diameter conjecture for bridgeless graphs

About 2 years old · traced to

Let GG be a bridgeless graph of order nn and minimum degree δ≥2\delta\geq 2, and let diam⁡→(G)\overrightarrow{\operatorname{diam}}(G) denote the minimum diameter over all strongly connected orientations of GG. Bau–Dankelmann's oriented diameter conjecture. There exists a constant CC such that

diam⁡→(G)≤3nδ+1+C.\overrightarrow{\operatorname{diam}}(G) \leq \frac{3n}{\delta+1}+C.

This conjecture asks for the asymptotically sharp upper bound suggested by the known lower bounds for bridgeless graphs. The paper proves an asymptotic result with coefficient 3+ϵ3+\epsilon and denominator δ−2\delta-2, while the conjectured bound with denominator δ+1\delta+1 and an additive constant remains open.

References

Primary source

Garner Cochran and Zhiyu Wang, “On the oriented diameter of graphs with given minimum degree”, arXiv:2409.06587 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.