ISSN:2164-6376 (print)
ISSN:2164-6414 (online)
Discontinuity, Nonlinearity, and Complexity

Dimitry Volchenkov (editor), Dumitru Baleanu (editor)

Dimitry Volchenkov(editor)

Mathematics & Statistics, Texas Tech University, 1108 Memorial Circle, Lubbock, TX 79409, USA

Email: dr.volchenkov@gmail.com

Dumitru Baleanu (editor)

Cankaya University, Ankara, Turkey; Institute of Space Sciences, Magurele-Bucharest, Romania

A Survey on Sufficient Conditions for Hamiltonian Cycles in Bipartite Digraphs

Discontinuity, Nonlinearity, and Complexity 11(1) (2022) 1--8 | DOI:10.5890/DNC.2022.03.001

Huifen Ge$^1$, Shumin Zhang$^{2}$, Chengfu Ye$^1$

$^1$ School of Computer, Qinghai Normal University, Xining 810001, China

$^{2}$ School of Mathematics and Statistics, Qinghai Normal University, Xining 810001, China

Abstract

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.  [1] Bang-Jensen, J. and Gutin, G. (2000), Digraphs: Theory, Algorithms and Applications, Springer.
2.  [2] Dirac, G.A. (1952), Some theorems on abstract graphs, London Math. Soc., 2(3), 69-81.
3.  [3] Diestel, R. (2016), Graph Theory, (fifth Edition), Springer.
4.  [4] Garey, M.R. and Johnson, D.S. (1979), Computers and intractability. W.H. Freeman. San Francisco.
5.  [5] Adamus, J. and Adamus, L. (2012), A degree condition for cycles of maximum length in bipartite digraphs, Discrete Mathematics, 312, 1117-1122.
6.  [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.  [7] Bermond, J.C. and Thomassen, C. (1981), Cycles in digraphs-a survey, J. Graph Theory, 5(1), 1-43.
8.  [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.  [9] Manoussakis, Y. and Milis, I. (1999), A sufficient condition for maximum cycles in bipartite digraphs, Discrete Mathematics, 207, 161-171.
10.  [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.  [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.  [12] Woodall, D.R. (1972), Sufficient conditions for circuits in graphs, Proceeding London Math. Society, 24, 739-755.
13.  [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.  [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.  [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.  [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.  [17] Wang, R., Chang, J., and Wu, L. (2020), A dominated pair condition for a digraph to be hamiltonian, Discrete Mathematics, 343, 111794.
18.  [18] H\"{a}ggkvist, R. and Manoussakis, Y. (1989), Cycles and paths in bipartite tournaments with spanning configurations, Combinatorica, 9(1), 33-38.
19.  [19] Zhong, W. (1992), A sufficient condition for hamiltonian cycles in bipartite tournaments, Australasian Journal of Combinatorics, 5, 299-304.
20.  [20] Gutin, G. (1995), Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey, J. Graph Theory, 19(4), 481-505.
21.  [21] Wang, R. (2017), A sufficient condition for a balanced bipartite digraph to be hamiltonian, Discrete Mathematics and Theoretical Computer science, 19(3).
22.  [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.  [23] Darbinyan, S.Kh. (2019), Sufficient conditions for hamiltonian cycles in bipartite digraphs, Discrete Applied Math, 258, 87-96.
24.  [24] Adamus, J. (2017), A degree sum condition for hamiltonicity in balanced bipartite digraphs, Graphs and Combinatorics, 33, 43-51.
25.  [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.  [26] Darbinyan, S.Kh. (1985), Pancyclicity of digraphs with the Meyniel condition, Studia Sci. Math. Hungar, 20(1-4), 95-117.
27.  [27] Darbinyan, S.Kh. (1986), On the pancyclicity of digraphs with large semidegrees, Akad. Nauk Arm. SSR Dokl., 83(3), 99-101.
28.  [28] H\"{a}ggkvist, R. and Thomassen, C. (1976), On pancyclic digraphs, Journal of Combinatorial Theory, Series B, 20(1), 20-40.
29.  [29] Overbeck-Larisch, M. (1977), A theorem on pancyclic-oriented graphs. Journal of Combinatorial Theory, Series B, 23, 168-173.
30.  [30] Thomassen, C. (1977), An Ore-type condition implying a digraph to be pancyclic, Discrete Mathematics, 19, 85-92.
31.  [31] Beineke, L.W. and Little, C. (1982), Cycles in bipartite tournaments. Journal of Combinatorial Theory Ser. B, 32(2), 140-145.
32.  [32] Zhang, K. (1981), Vertex even-pancylicity in bipartite tournaments, J. Nanjing Univ. Math. Biquarterly, 1, 85-88.
33.  [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.  [34] Gutin, G. (1995), Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs, Discrete Mathematics, 141, 153-162.
35.  [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.  [36] Meszka, M. (2018), New sufficient conditions for bipancyclicity of balanced bipartite digraphs, Discrete Mathematics, 341, 3237-3240.
37.  [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.  [38] Adamus, J. (2018), A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs, Graphs and Combinatorics, 34, 703-709.
39.  [39] Darbinyan, S.Kh. (2018), Sufficient conditions for balanced bipartite digraphs to be even pancyclic, Discrete Applied Math, 238, 70-76.
40.  [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.