Improved bound on the oriented diameter of graphs with given minimum degree

In 2015, Bau and Dankelmann showed that every bridgeless graph GG of order nn and minimum degree δδ has an orientation of diameter at most 11nδ+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 GG has an orientation of diameter less than 7nδ+1 and give a polynomial-time algorithm to construct one.