[ Log In | Register]
! Skip Navigation Links
Skip Navigation Links
Image of Discontinuity, Nonlinearity and Complexity
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

Email: dumitru.baleanu@gmail.com

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

Download Full Text PDF

 

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.

Copyright © 2011-2023 L & H Scientific Publishing. All rights reserved. Wildcard SSL Certificates