Conjecture on oriented diameter of bridgeless graphs of diameter at most 3

All graphs considered are finite and simple. An orientation of a graph GG 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 33 has oriented diameter at most 99.

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

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.