Oriented diameter of graphs with given maximum degree
Peter Dankelmann, Yubao Guo, Michel Surmacs · Journal of Graph Theory · 2017
Abstract In this article, we show that every bridgeless graph G of order n and maximum degree Δ has an orientation of diameter at most . We then use this result and the definition , 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 , if e is on a triangle and at most , otherwise. Furthermore, for every bridgeless subgraph H of G, there is such an orientation of diameter at most . Finally, if G is bipartite, then we show the existence of an orientation of diameter at most , for every partite set A of G and . This particularly implies that balanced bipartite graphs have an orientation of diameter at most . 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.