论文标题
Chvátal和Thomassen的上限改进了定向直径
An Improvement to Chvátal and Thomassen's Upper Bound for Oriented Diameter
论文作者
论文摘要
无向图$ g $的方向是$ g $的每个边缘的一个方向。图$ g $的定向直径是$ g $的所有方向中最小的直径。图形系列$ \ mathscr {f} $的最大定向直径是$ \ m rathscr {f} $中所有图的最大方向直径。 Chvátal和Thomassen [JCTB，1978年]给出了$ \ frac {1} {2} {2} d^2+d $和$ 2D^2+2d $的上限，用于$ 2 $ 2 $ - edge connected Diameter Graphs of Diimeter $ d $ d $ d $的最大定向直径。我们将此上限提高到$ 1.373 d^2 + 6.971d-1 $，这在所有$ d $的所有值大于或等于$ 8 $的情况下优于以前的上限。对于$ 2 $ - 边缘连接的直径图$ 3 $的家族，Kwok，Liu和West [JCTB，2010年]的下限和上限分别为$ 9 $和$ 11 $。对于$ 2 $ - 边缘连接的直径图$ 4 $的家族，Chvátal和Thomassen提供的边界为$ 12 $和40美元，并且不知道更好的界限。通过扩展我们用于直径$ d $图的方法，以及Chvátal和Thomassen使用的技术的不对称扩展，我们将这一上限提高到了$ 21 $。
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 $\mathscr{F}$ is the maximum oriented diameter among all the graphs in $\mathscr{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.373 d^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$.
