Large Girth and Small Oriented Diameter Graphs

Abstract

In 2015, Dankelmann and Bau proved that for every bridgeless graph $G$ of order $n$ and minimum degree $\delta$ there is an orientation of diameter at most $11\frac{n}{\delta +1}+9$. In 2016, Surmacs reduced this bound to $7\frac{n}{\delta +1}.$ In this paper, we consider the girth of a graph $g$ and show that for any $\epsilon >0$ there is a bound of the form $(2g+\epsilon )\frac{n}{h(\delta ,g)}+O(1)$, where $h(\delta ,g)$ is a polynomial. Letting $g=3$ and $\epsilon <1$ gives an inprovement on the result by Surmacs.

14 pages, 2 figures