On the oriented diameter of graphs with given minimum degree

Abstract

Erdős, Pach, Pollack, and Tuza [\textit{J. Combin. Theory Ser. B, 47(1) (1989), 73-79}] proved that the diameter of a connected $n$-vertex graph with minimum degree $\hat{I}´$ is at most $\frac{3n}{\hat{I}´+1}+O(1)$. The oriented diameter of an undirected graph $G$, denoted by $\overrightarrow{\text{diam}}(G)$, is the minimum diameter of a strongly connected orientation of $G$. Bau and Dankelmann [\textit{European J. Combin., 49 (2015), 126-133}] showed that for every bridgeless $n$-vertex graph $G$ with minimum degree $\hat{I}´$, $\overrightarrow{\text{diam}}(G)\le \frac{11n}{\hat{I}´+1}+9$. They also showed an infinite family of graphs with oriented diameter at least $\frac{3n}{\hat{I}´+1}+O(1)$ and posed the problem of determining the smallest possible value $c$ for which $\overrightarrow{\text{diam}}(G)\le c\cdot \frac{3n}{\hat{I}´+1}+O(1)$ holds. In this paper, we show that the smallest value $c$ such that the upper bound above holds for all $\hat{I}´\ge 2$ is $1$, which is best possible.

16 pages, 6 figures