Bau–Dankelmann oriented diameter conjecture for bridgeless graphs

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.