The oriented discrepancy of Hamiltonian cycles in a Hamiltonian graph $ G $ of order $ n $ is the largest integer $ \ell $ such that every orientation $ D $ of $ G $ contains a Hamiltonian oriented cycle $ C $ satisfying $ \sigma_{\max}(C)\ge\lceil(n+\ell)/2\rceil $, where $ \sigma_{\max}(C) $ denotes the maximum of the numbers of forward and backward arcs of $ C $. For a vertex $ w $ in an oriented graph $ D $, let $ d(w) $ denote the degree of $ w $ in the underlying graph of $ D $. Ai, Guo, Gutin, Lan, Shao, Yeo and Zhou [AIMS Math. 11 (2026), 24106-24119] proved that, for any positive integer $ k $, every oriented graph $ D $ of order $ n\ge30+4(k-1) $ with $ s^{*}(D)\ge8k $ contains a Hamilton oriented cycle $ C $ satisfying $ \sigma_{\max}(C)\ge\lceil(n+k)/2\rceil $, where $ s^{*}(D) $ is the minimum of $ d(u)+d(v)-n $ over all distinct non-adjacent vertices $ u, v $ of $ D $ when $ D $ is not a tournament, while $ s^{*}(D) = n-2 $ when $ D $ is a tournament. They asked whether the factor $ 8 $ in the bound $ s^{*}(D)\ge8k $ can be reduced. For every $ k\ge6 $, we prove that the aforementioned conclusion follows from $ s^{*}(D)\ge4k-3 $; however, when $ n+k $ is even and $ k\ge7 $, then the condition $ s^{*}(D)\ge4k-7 $ is sufficient. We also obtain results for $ 1\le k\le5 $. Moreover, for every fixed positive integer $ k $ and all sufficiently large $ n $, we prove that the same conclusion follows from $ s^{*}(D)\ge3k $ when $ n+k $ is odd and from $ s^{*}(D)\ge3k-3 $ when $ n+k $ is even.
Citation: Akbar Ali, Abdulaziz Mutlaq Alotaibi. On Ore-type conditions for oriented discrepancy of Hamilton cycles[J]. AIMS Mathematics, 2026, 11(10): 34107-34118. doi: 10.3934/math.20261330
The oriented discrepancy of Hamiltonian cycles in a Hamiltonian graph $ G $ of order $ n $ is the largest integer $ \ell $ such that every orientation $ D $ of $ G $ contains a Hamiltonian oriented cycle $ C $ satisfying $ \sigma_{\max}(C)\ge\lceil(n+\ell)/2\rceil $, where $ \sigma_{\max}(C) $ denotes the maximum of the numbers of forward and backward arcs of $ C $. For a vertex $ w $ in an oriented graph $ D $, let $ d(w) $ denote the degree of $ w $ in the underlying graph of $ D $. Ai, Guo, Gutin, Lan, Shao, Yeo and Zhou [AIMS Math. 11 (2026), 24106-24119] proved that, for any positive integer $ k $, every oriented graph $ D $ of order $ n\ge30+4(k-1) $ with $ s^{*}(D)\ge8k $ contains a Hamilton oriented cycle $ C $ satisfying $ \sigma_{\max}(C)\ge\lceil(n+k)/2\rceil $, where $ s^{*}(D) $ is the minimum of $ d(u)+d(v)-n $ over all distinct non-adjacent vertices $ u, v $ of $ D $ when $ D $ is not a tournament, while $ s^{*}(D) = n-2 $ when $ D $ is a tournament. They asked whether the factor $ 8 $ in the bound $ s^{*}(D)\ge8k $ can be reduced. For every $ k\ge6 $, we prove that the aforementioned conclusion follows from $ s^{*}(D)\ge4k-3 $; however, when $ n+k $ is even and $ k\ge7 $, then the condition $ s^{*}(D)\ge4k-7 $ is sufficient. We also obtain results for $ 1\le k\le5 $. Moreover, for every fixed positive integer $ k $ and all sufficiently large $ n $, we prove that the same conclusion follows from $ s^{*}(D)\ge3k $ when $ n+k $ is odd and from $ s^{*}(D)\ge3k-3 $ when $ n+k $ is even.
| [1] |
J. Ai, Q. Guo, G. Gutin, Y. Lan, Q. Shao, A. Yeo, et al., Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition, AIMS Math., 11 (2026), 24106–24119. https://doi.org/10.3934/math.2026972 doi: 10.3934/math.2026972
|
| [2] | A. Ali, I. Gutman, E. Milovanović, I. Milovanović, Sum of powers of the degrees of graphs: Extremal results and bounds, Match. Commun. Math. Comput. Chem., 80 (2018), 5–84. Available from: https://match.pmf.kg.ac.rs/electronic_versions/Match80/n1/match80n1_5-84.pdf |
| [3] |
B. Bollobás, V. Nikiforov, Books in graphs, European J. Combin., 26 (2005), 259–270. https://doi.org/10.1016/j.ejc.2004.01.007 doi: 10.1016/j.ejc.2004.01.007
|
| [4] | B. Borovićanin, K. C. Das, B. Furtula, I. Gutman, Bounds for Zagreb indices, Match Commun. Math. Comput. Chem., 78 (2017), 17–100. Available from: https://match.pmf.kg.ac.rs/electronic_versions/Match78/n1/match78n1_17-100.pdf |
| [5] | Y. F. Chang, Y. Y. Cheng, Z. L. Wang, S. Wei, J. Yan, An Ore-type theorem for oriented discrepancy of Hamilton cycles, arXiv: 2603.18915, 2026. https://doi.org/10.48550/arXiv.2603.18915 |
| [6] |
G. A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc., s3-2 (1952), 69–81. https://doi.org/10.1112/plms/s3-2.1.69 doi: 10.1112/plms/s3-2.1.69
|
| [7] |
A. Freschi, A. Lo, An oriented discrepancy version of Dirac's theorem, J. Combin. Theory Ser. B, 169 (2024), 338–351. https://doi.org/10.1016/j.jctb.2024.06.008 doi: 10.1016/j.jctb.2024.06.008
|
| [8] |
L. Gishboliner, M. Krivelevich, P. Michaeli, Oriented discrepancy of Hamilton cycles, J. Graph Theory, 103 (2023), 780–792. https://doi.org/10.1002/jgt.22947 doi: 10.1002/jgt.22947
|
| [9] |
O. Ore, Note on Hamilton circuits, Amer. Math. Monthly, 67 (1960), 55–55. https://doi.org/10.2307/2308928 doi: 10.2307/2308928
|
| [10] | C. S. Edwards, A lower bound for the largest number of triangles with a common edge, unpublished manuscript, 1977. |
| [11] |
M. Simonovits, Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, Discrete Math., 7 (1974), 349–376. https://doi.org/10.1016/0012-365X(74)90044-2 doi: 10.1016/0012-365X(74)90044-2
|