A Survey on Sufficient Conditions for Hamiltonian Cycles in Bipartite Digraphs
DOI:
https://doi.org/10.5890/DNC.2022.03.001Abstract
A digraph $D=(V,A)$ is called a bipartite digraph if there exists a partition $(X,Y)$ of $V(D)$ into two partite sets such that every arc of $D$ has its end-vertices in different partite sets. It is called balanced if $|X| = |Y|$. If a digraph $D$ has a directed cycle $C$ which covers all of its vertices, then $D$ is Hamiltonian. This paper mainly introduces some sufficient conditions for Hamiltonian cycles in balanced bipartite digraph.References
[1] Bang-Jensen, J. and Gutin, G. (2000), Digraphs: Theory, Algorithms and Applications, Springer.
[2] Dirac, G.A. (1952), Some theorems on abstract graphs, London Math. Soc., 2(3), 69-81.
[3] Diestel, R. (2016), Graph Theory, (fifth Edition), Springer.
[4] Garey, M.R. and Johnson, D.S. (1979), Computers and intractability. W.H. Freeman. San Francisco.
[5] Adamus, J. and Adamus, L. (2012), A degree condition for cycles of maximum length in bipartite digraphs, Discrete Mathematics, 312, 1117-1122.
[6] Adamus, J., Adamus, L., and Yeo, A. (2014), On the Meyniel condition for hamiltonicity in bipartite digraphs, Discrete Math and Theoretical Computer Science, 16, 293-302.
[7] Bermond, J.C. and Thomassen, C. (1981), Cycles in digraphs-a survey, J. Graph Theory, 5(1), 1-43.
[8] Amar, D. and Manoussakis, Y. (1990), Cycles and paths of many lengths in bipartite digraphs, Journal of Combinatorial Theory Ser. B., 50, 254-264.
[9] Manoussakis, Y. and Milis, I. (1999), A sufficient condition for maximum cycles in bipartite digraphs, Discrete Mathematics, 207, 161-171.
[10] Ghouila-Houri, A. (1960), Une condition suffisante d'existence d'un circuit hamiltonien, Rendus de I' Academie des Sciences Paris Ser. A-B, 25, 495-497.
[11] Nash-Williams, C.St.J.A. (1969), Hamilton circuits in graphs and digraphs, in ``The many facets of graph theory'', Springer, Lecture Notes, 110, 237-243.
[12] Woodall, D.R. (1972), Sufficient conditions for circuits in graphs, Proceeding London Math. Society, 24, 739-755.
[13] Meyniel, M. (1973), condition suffisante d'existence d'un circuit hamiltonien dans un graphe oriente, Journal Combinatorial Theory Ser. B, 14, 137-147.
[14] Bang-Jensen, J., Gutin, G., and Li, H. (1996), Sufficient conditions for a digraph to be hamiltonian, J. Graph Theory, 22(2), 181-187.
[15] Bang-Jensen, J., Guo, Y., and Yeo, A. (1999), A new sufficient condition for a digraph to be hamiltonian, Discrete Applied Math., 95, 61-72.
[16] Wang, R. and Wu, L. (2020), A dominating pair condition for a balanced bipartite digraph to be hamiltonian, Australasian Journal of Combinatorics, 77, 136-143.
[17] Wang, R., Chang, J., and Wu, L. (2020), A dominated pair condition for a digraph to be hamiltonian, Discrete Mathematics, 343, 111794.
[18] H"{a}ggkvist, R. and Manoussakis, Y. (1989), Cycles and paths in bipartite tournaments with spanning configurations, Combinatorica, 9(1), 33-38.
[19] Zhong, W. (1992), A sufficient condition for hamiltonian cycles in bipartite tournaments, Australasian Journal of Combinatorics, 5, 299-304.
[20] Gutin, G. (1995), Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey, J. Graph Theory, 19(4), 481-505.
[21] Wang, R. (2017), A sufficient condition for a balanced bipartite digraph to be hamiltonian, Discrete Mathematics and Theoretical Computer science, 19(3).
[22] Darbinyan, S.Kh. and Karapetyan, I.A. (2018), On a problem of Wang concerning the hamiltonicity of bipartite digraphs, Mathematical Problems of Computer Science, 49, 26-34.
[23] Darbinyan, S.Kh. (2019), Sufficient conditions for hamiltonian cycles in bipartite digraphs, Discrete Applied Math, 258, 87-96.
[24] Adamus, J. (2017), A degree sum condition for hamiltonicity in balanced bipartite digraphs, Graphs and Combinatorics, 33, 43-51.
[25] Chv{a}tal, V. (1973), New directions in hamiltonian graph theory, in New directions in the theory of graphs (F. Harary, ed.). Academic Press, New York. 5(1), 65-95.
[26] Darbinyan, S.Kh. (1985), Pancyclicity of digraphs with the Meyniel condition, Studia Sci. Math. Hungar, 20(1-4), 95-117.
[27] Darbinyan, S.Kh. (1986), On the pancyclicity of digraphs with large semidegrees, Akad. Nauk Arm. SSR Dokl., 83(3), 99-101.
[28] H"{a}ggkvist, R. and Thomassen, C. (1976), On pancyclic digraphs, Journal of Combinatorial Theory, Series B, 20(1), 20-40.
[29] Overbeck-Larisch, M. (1977), A theorem on pancyclic-oriented graphs. Journal of Combinatorial Theory, Series B, 23, 168-173.
[30] Thomassen, C. (1977), An Ore-type condition implying a digraph to be pancyclic, Discrete Mathematics, 19, 85-92.
[31] Beineke, L.W. and Little, C. (1982), Cycles in bipartite tournaments. Journal of Combinatorial Theory Ser. B, 32(2), 140-145.
[32] Zhang, K. (1981), Vertex even-pancylicity in bipartite tournaments, J. Nanjing Univ. Math. Biquarterly, 1, 85-88.
[33] Gutin, G. (1989), A characterization of vertex pancyclic partly oriented k-partite tournaments, Vestsi Acad. Navuk BSSR Ser. Fiz.-Mat. Navuk, 2, 41-46.
[34] Gutin, G. (1995), Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs, Discrete Mathematics, 141, 153-162.
[35] Darbinyan, S.Kh. and Karapetyan, I.A. (2017), On longest non-hamiltonian cycles in digraphs with the conditions of Bang-Jensen, Gutin and Li, Discrete Applied Mathematics, 216, 537-549.
[36] Meszka, M. (2018), New sufficient conditions for bipancyclicity of balanced bipartite digraphs, Discrete Mathematics, 341, 3237-3240.
[37] Darbinyan, S.Kh. and Karapetyan, I.A. (2017), A sufficient condition for pre-hamiltonian cycles in bipartite digraphs, Eleventh International Conference on Computer Science and Information Technologies(CSIT), 101-109.
[38] Adamus, J. (2018), A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs, Graphs and Combinatorics, 34, 703-709.
[39] Darbinyan, S.Kh. (2018), Sufficient conditions for balanced bipartite digraphs to be even pancyclic, Discrete Applied Math, 238, 70-76.
[40] Wang, R. and Guo, J. (2017), A note on cycles of maximum length in bipartite digraphs, Australasian Journal of Combinatorics, 67(1), 1-10.
Article Metrics
Usage tracking begins September 1, 2026.