Conjecture on oriented diameter of bridgeless graphs of diameter at most 3
Conjecture on oriented diameter of bridgeless graphs of diameter at most 3
All graphs considered are finite and simple. An orientation of a graph is obtained by replacing each edge by one of the two possible arcs with the same ends. The oriented diameter of a bridgeless graph is the minimum diameter among its orientations. A graph is bridgeless if it has no cut-edge.
Diameter-three oriented-diameter conjecture. Every bridgeless graph with diameter at most has oriented diameter at most .
The paper derives the bound for several classes of spanning subgraphs and proposes the statement as the remaining general case. No resolution is supplied in the source.
Sources & referencesView supporting material
Primary source
Hengzhe Li, Xueliang Li, Yuefang Sun and Jun Yue, “Note on the oriented diameter of graphs with diameter 3”, arXiv:1109.1056 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.