Bau–Dankelmann oriented diameter conjecture for bridgeless graphs
Bau–Dankelmann oriented diameter conjecture for bridgeless graphs
Let be a bridgeless graph of order and minimum degree , and let denote the minimum diameter over all strongly connected orientations of . Bau–Dankelmann's oriented diameter conjecture. There exists a constant such that
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 and denominator , while the conjectured bound with denominator 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
Sign in to submit a solution.
No solutions have been posted yet.