An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter

Abstract

An orientation of an undirected graph $G$ is an assignment of exactly one direction to each edge of $G$. The oriented diameter of a graph $G$ is the smallest diameter among all the orientations of $G$. The maximum oriented diameter of a family of graphs $\mathcal{F}$ is the maximum oriented diameter among all the graphs in $\mathcal{F}$. Chvátal and Thomassen [JCTB, 1978] gave a lower bound of $\frac{1}{2}{d}^2+d$ and an upper bound of $2d^2+2d$ for the maximum oriented diameter of the family of $2$-edge connected graphs of diameter $d$. We improve this upper bound to $1.373d^2+6.971d-1$, which outperforms the former upper bound for all values of $d$ greater than or equal to $8$. For the family of $2$-edge connected graphs of diameter $3$, Kwok, Liu and West [JCTB, 2010] obtained improved lower and upper bounds of $9$ and $11$ respectively. For the family of $2$-edge connected graphs of diameter $4$, the bounds provided by Chvátal and Thomassen are $12$ and $40$ and no better bounds were known. By extending the method we used for diameter $d$ graphs, along with an asymmetric extension of a technique used by Chvátal and Thomassen, we have improved this upper bound to $21$.

10 pages, LaTeX; Corrected typos, Changed a reference, Revised arguments in sections 2.1 and 3.3, Results unchanged