Journal of the Operations Research Society of China ›› 2025, Vol. 13 ›› Issue (2): 574-589.doi: 10.1007/s40305-023-00476-2

Previous Articles     Next Articles

Using the minimum and maximum degrees to bound the diameter of orientations of bridgeless graphs

Wan-Ping Zhang, Ji-Xiang Meng, Baoyindureng Wu   

  1. College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, Xinjiang, China
  • Received:2022-05-28 Revised:2023-02-10 Online:2025-06-30 Published:2025-07-07
  • Contact: Ji-Xiang Meng E-mail:mjxxju@sina.com
  • Supported by:
    This work was supported by the Natural Science Foundation of Xinjiang (No. 2020D04046), the National Natural Science Foundation of China (No. 12061073).

Abstract: 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.

Key words: Orientation, Diameter, Minimum degree, Maximum degree, Girth, Packing, Bridgeless graph

CLC Number: