On pre-Hamiltonian Cycles in Balanced Bipartite Digraphs
Keywords:
Digraphs, Cycles, Hamiltonian cycle, Bipartite balanced digraph, Pancyclic, Even pancyclicAbstract
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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
