Research article Special Issues

On Ore-type conditions for oriented discrepancy of Hamilton cycles

  • Published: 20 October 2026
  • MSC : 05C20, 05C45

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)

Metrics

Article views(81) PDF downloads(9) Cited by(0)

Article outline

Figures and Tables

Figures(2)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog