## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 5-17 |

Number of pages | 13 |

Journal | Journal of Graph Theory |

Volume | 88 |

Issue number | 1 |

DOIs | |

Publication status | Published - May 2018 |

## Keywords

- AMS subject classifications
- maximum degree
- oriented diameter
- strongly connected orientation

## ASJC Scopus subject areas

- Geometry and Topology