On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs


  • Samvel Kh. Darbinyan Institute for Informatics and Automation Problems of NAS RA


Digraphs, Cycles, Hamiltonian cycle, Bipartite balanced digraph, Pancyclic, Even pancyclic


Let D be a strongly connected balanced bipartite directed graph of order 2a ≥ 10. Let x, y be distinct vertices in D. {x, y} dominates a vertex z if x → z and y → z; in this case, we call the pair {x, y} dominating. In this paper we prove:
If max{d(x), d(y)} ≥ 2a-2 for every dominating pair of vertices {x, y}, then either the underlying graph of D is 2-connected or D contains a cycle of length 2a - 2 or D is isomorphic to one digraph of order ten.


J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2001.

A. Ghouila-Houri, “Une condition suffisante d'existence d'un circuit hamiltonien", Comptes Rendus de I'Academie des Sciences Paris Ser. A-B, vol. 25, pp. 495-497, 1960.

C.St.J.A. Nash-Williams, “Hamilton circuits in graphs and digraphs", in The many facets of graph theory, Springer Verlag Lecture Notes, vol. 110, pp. 237-243, 1969.

D. R. Woodall, “Sufficient conditions for circuits in graphs", Proceeding London Mathematical Society, vol. 24, pp. 739-755, 1972.

M. Meyniel, “Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe oriente", Journal of Combinatorial Theory Ser. B, vol. 14, pp. 137-147, 1973.

C. Thomassen, “Long cycles in digraphs", Proceeding London Mathematical Society, vol. 3, no. 42, pp. 231-251, 1981.

M. Ovrebek-Larisch, “A theorem on pancyclic oriented graphs", Journal of Combinatorial Theory Ser. B, vol. 21, no. 1, pp. 76-80, 1976.

R. Häggkvist, C. Thomassen, “On pancyclic digraphs", Journal of Combinatorial Theory Ser. B, vol. 20, no. 1, pp. 20-40, 1976.

C. Thomassen, “An Ore-type condition implying a digraph to be pancyclic", Discrete Mathematics, vol. 19, no. 1, pp. 85-92, 1977.

S.Kh. Darbinyan, “On pancyclic digraphs", Pereprint of the Computing Centre of the Akademy Nauk Armyan. SSR 21 pp., 1979.

S.Kh. Darbinyan, “Pancyclicity of digraphs with the Meyniel condition", Studia Scientiarum Mathematicarum Hungarica, vol. 20, no. 1-4, pp. 95-117, 1985 (in Russian) (Ph.D. Thesis, Institute Mathematici Akademy Nauk BSSR, Minsk, 1981).

S.Kh. Darbinyan, “On the pancylicity of digraphs with large semidegrees", Akademy Nauk Armyan. SSR Doklady, vol. 83, no. 3, pp. 99-101, 1986 (see also arXiv: 1111.1841 v1 [math.CO] 8 Nov 2011).

J. Bang-Jensen, G. Gutin and H. Li, “Sufficient conditions for a digraph to be Hamiltonian", Journal of Graph Theory, vol. 22, no. 20, pp. 181-187, 1996.

J. Bang-Jensen, Y. Guo and A.Yeo, “A new sufficient condition for a digraph to be Hamiltonian", Discrete Applied Mathematics, vol. 95, pp. 61-72, 1999.

J. Adamus, L. Adamus and A. Yeo, “On the Meyniel condition for hamiltonicity in bipartite digraphs", Discrete Math.Theor. Comput. Sci., vol. 16, pp. 293-302, 2014.

R. Wang, “A sufficient condition for a balanced bipartite digraph to be hamiltonian", arX Iv:15 06.07949 [math. CO] 26 jun 2015.

S. Kh. Darbinyan, “ Sufficient conditions for hamiltonian cycles in bipartite digraphs", arXiv: 1604.08733v1 [math.CO] 29 Apr 2016.

S.Kh. Darbinyan, “Cycles of each even lengths in balanced bipartite digraphs", arXiv: 1604.08733v1 [math.CO] 14 Jul 2016.




How to Cite

Darbinyan, S. K. (2021). On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs. Mathematical Problems of Computer Science, 46, 7–17. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/142