2024/09/10 by Cochran, Garner, Wang, Zhiyu
#05C12 #05C20 #05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.06587
Erdős, Pach, Pollack, and Tuza [J. Combin. Theory Ser. B, 47(1) (1989), 73-79] proved that the diameter of a connected n-vertex graph with minimum degree δ is at most (3n)/(δ+1)+O(1). The oriented diameter of an undirected graph G, denoted by \overrightarrowdiam(G), is the minimum diameter of a strongly connected orientation of G. Bau and Dankelmann [European J. Combin., 49 (2015), 126-133] showed that for every bridgeless n-vertex graph G with minimum degree δ, \overrightarrowdiam(G) ≤ (11n)/(δ+1)+9. They also showed an infinite family of graphs with oriented diameter at least (3n)/(δ+1) + O(1) and posed the problem of determining the smallest possible value c for which \overrightarrowdiam(G) ≤ c ⋅(3n)/(δ+1)+O(1) holds. In this paper, we show that the smallest value c such that the upper bound above holds for all δ≥ 2 is 1, which is best possible.