Oriented diameter of graphs with given maximum degree

In this article, we show that every bridgeless graph G of order n and maximum degree Δ has an orientation of diameter at most n – Δ + 3. We then use this result and the definition N_G(H) = U∈(H) N_G(v)\V(H), for every subgraph H of G, to give better bounds in the case that G contains certain clusters of high-degree vertices, namely: For every edge e, G has an orientation of diameter at most n −|_G(e)| + 4, if e is on a triangle and at most n −|_G(e)| + 5, otherwise. Furthermore, for every bridgeless subgraph H of G, there is such an orientation of diameter at most n −|_G(e)| + 3. Finally, if G is bipartite, then we show the existence of an orientation of diameter at most 2(|A| − deg_G(S) + 7, for every partite set A of G and s∈ V(G). This particularly implies that balanced bipartite graphs have an orientation of diameter at most n – 2Δ + 3. For each bound, we give a polynomial-time algorithm to construct a corresponding orientation and an infinite family of graphs for which the bound is sharp.