2022/01/19 by Cochran, Garner · 2 citations
#05C12 #05C20 #05C85 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2201.07618
In 2015, Dankelmann and Bau proved that for every bridgeless graph G of order n and minimum degree δ there is an orientation of diameter at most 11(n)/(δ+1)+9. In 2016, Surmacs reduced this bound to 7(n)/(δ+1). In this paper, we consider the girth of a graph g and show that for any ε>0 there is a bound of the form (2g+ε)(n)/(h(δ,g))+O(1), where h(δ,g) is a polynomial. Letting g=3 and ε<1 gives an inprovement on the result by Surmacs.