Improved bound on the oriented diameter of graphs with given minimum degree. (January 2017) - Surmacs, Michel
Abstract: In 2015, Bau and Dankelmann showed that every bridgeless graph G of order n and minimum degree δ has an orientation of diameter at most 11 n δ + 1 + 9 . As they were convinced that this bound is not best possible, they posed the problem of improving it. In this paper, we prove that such a graph G has an orientation of diameter less than 7 n δ + 1 and give a polynomial-time algorithm to construct one.