The oriented diameter of an undirected graph G, denoted by \begin{document}$ \textrm{diam}(\overrightarrow{G}) $\end{document}, is defined as the minimum diameter of any strong orientation of G. In this paper, we prove that the oriented diameter of a bridgeless \begin{document}$ C_{4} $\end{document}-free graph is at most \begin{document}$ \frac{37n}{\delta ^2-2\lfloor \delta /2\rfloor +1}+19 $\end{document}. We also consider some upper bounds of \begin{document}$ \textrm{diam}(\overrightarrow{G}) $\end{document} in terms of girth g, minimum degree \begin{document}$ \delta $\end{document} and maximum degree \begin{document}$ \Delta $\end{document} and give some upper bounds of \begin{document}$ \textrm{diam}(\overrightarrow{G}) $\end{document} in bridgeless \begin{document}$ (C_{4},C_{5}) $\end{document}-free graphs.
Wan-Ping Zhang, Ji-Xiang Meng, Baoyindureng Wu
. Using the minimum and maximum degrees to bound the diameter of orientations of bridgeless graphs[J]. Journal of the Operations Research Society of China, 2025
, 13(2)
: 574
-589
.
DOI: 10.1007/s40305-023-00476-2
[1] Surmacs, M.: Improved bound on the oriented diameter of graphs with given minimum degree. Eur. J. Combin. 59, 187-191 (2017)
[2] Chvátal, V., Thomassen, C.: Distances in orientations of graphs. J. Combin. Theory Ser. B 24, 61-75 (1978)
[3] Egawa, Y., Iida, T.: Orientation of 2-edge-connected graphs with diameter 3. Far East J. Appl. Math. 26, 257-280 (2007)
[4] Kwok, P.K., Liu, Q., West, D.B.: Oriented diameter of graphs with diameter 3. J. Combin. Theory Ser. B 100, 265-274 (2010)
[5] Babu, J., Benson, D., Rajendraprasad, D., Vaka, S.N.: An improvement to Chvátal and Thomassen’s upper bound for oriented diameter. Discrete Appl. Math. 304, 432-440 (2021)
[6] Šltés, L.: Orientations of graphs minimizing the radius of the diameter. Math. Slovaca 36, 289-296 (1986)
[7] Plesník, J.: Remarks on the diameters of orientations of graphs. Acta Math. Univ. Comenianae. 46-47, 225-236 (1985)
[8] Gutin, G.: Minimizing and maximizing the diameter of orientations of graphs. Graphs Combin. 10, 225-230 (1994)
[9] Fomin, F.V., Matamala, M., Prisner, E.: Rapaport I. AT-free graphs: linear bounds for the oriented diameter. Discrete Appl. Math. 141, 135-148 (2004)
[10] Kurz, S., Lätsch, M.: Bounds for the minimum oriented diameter. Discrete Math. Theor. Comput. Sci. 14, 109-140 (2012)
[11] Erdös, P., Pach, J., Pollack, R., Tuza, Z.: Radius, diameter, and minimum degree. J. Combin. Theory Ser. B 47, 73-79 (1989)
[12] Dankelmann, P., Guo, Y., Surmacs, M.: Oriented diameter of graphs with given maximum degree. J. Graph Theory. 88, 5-17 (2018)
[13] Wang, X., Chen, Y., Dankelmann, P., Guo, Y., Surmacs, M., Volkmann, L.: Oriented diameter of maximal outerplanar graphs. J. Graph Theory. 98, 426-444 (2021)
[14] Bau, S., Dankelmann, P.: Diameter of orientations of graphs with given minimum degree. Eur. J. Combin. 49, 126-133 (2015)
[15] Koh, K.M., Ng, K.L.: The orientation number of two complete graphs with linkages. Discrete Math. 295, 91-106 (2005)
[16] Gutin, G., Yeo, A.: Orientations of digraphs almost preserving diameter. Discrete Appl. Math. 121, 129-138 (2002)
[17] Koh, K.M., Tay, E.G.: Optimal orientations of graphs and digraphs a survey. Gr. Combin. 18, 745-756 (2002)
[18] Lakshmi, R.: Optimal orientation of the tensor product of a small diameter graph and a complete graph. Austral. J. Combin. 50, 165-169 (2011)
[19] Alochukwu, A., Dankelmann, P.: Distances in graphs of girth 6 and generalised cages. Discrete Appl. Math. 294, 125-137 (2021)
