A Theorem on Even Pancyclic Bipartite Digraphs
DOI:
https://doi.org/10.51408/1963-0069Keywords:
Digraphs, Hamiltonian cycles, Bipartite digraphs, Pancyclic, Even pancyclicAbstract
We prove a Meyniel-type condition and a Bang-Jensen, Gutin and Li-type condition for a strongly connected balanced bipartite digraph to be even pancyclic. Let D be a balanced bipartite digraph of order 2a ≥ 6. We prove that
(i) If d(x)+d(y) ≥ 3a for every pair of vertices x, y from the same partite set, then D contains cycles of all even lengths 2, 4, . . . , 2a, in particular, D is Hamiltonian.
(ii) If D is other than a directed cycle of length 2a and d(x) + d(y) ≥ 3a for every pair of vertices x, y with a common out-neighbor or in-neighbor, then either D contains cycles of all even lengths 2, 4, . . . , 2a or d(u) + d(v) ≥ 3a for every pair of vertices u, v from the same partite set. Moreover, by (i), D contains cycles of all even lengths 2, 4, . . . , 2a, in particular, D is Hamiltonian.
References
J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2000.
J. Adamus, “A degree sum condition for hamiltonicity in balanced bipartite digraphs”, Graphs and Combinatorics, vol. 33, no. 1, pp. 43-51, 2017.
J. Adamus, L. Adamus and A. Yeo, “On the Meyniel condition for hamiltonicity in bipartite digraphs”, Discrete Mathematics and Theoretical Computer Science, vol. 16 no. 1, pp. 293-302, 2014.
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. Bang-Jensen, G. Gutin and H. Li, “Sufficient conditions for a digraph to be hamiltonian”, Journal of Graph Theory, vol. 22, no. 2, pp. 181-187, 1996.
J.-C. Bermond and C. Thomassen, “Cycles in digraphs - A survey”, Journal of Graph Theory, vol. 5, no. 1, pp. 1-43, 1981.
A. Ghouila-Houri, “Une condition suffisante d’existence d’un circuit hamiltonien”, Comptes Rendus de I’ Academie des Science Paris Ser. A-B, vol. 25, pp. 495-497, 1960.
G. Gutin, “Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey”, Journal of Graph Theory, vol. 19, no. 4, pp. 481-505, 1995.
D. Kühn and D. Osthus, “A survey on Hamilton cycles in directed graphs”, European Journal of Combinatorics, vol. 33, no. 5, pp. 750-766, 2012.
M. Meyniel, “Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente”, Journal Combinatorial Theory Ser. B, vol. 14, pp. 137-147, 1973.
S.Kh. Darbinyan, “Pancyclicity of digraphs with the Meyniel condition”, Studia Scientiarum Mathematicarum Hungarica, vol. 20, no. 1-4, pp. 97-117, 1985 (Ph.D. Thesis, Institute Mathematici Akad. Nauk BSSR, Minsk, 1981) (in Russian).
S.Kh. Darbinyan, “On the pancyclicity of digraphs with large semidegrees”, Akademy Nauk Armyan SSR Dokllady, vol. 83, no. 3, pp. 99-101, 1986 (arXiv: 1111.1841v1).
R. Häggkvist and C. Thomassen, “On pancyclic digraphs”, Journal 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, pp. 85-92, 1977.
M. Meszka, “New sufficient conditions for bipancyclicity of balanced bipartite digraphs”, Discrete Mathematics, vol. 341, no. 11, pp. 3237-3240, 2018.
R. Wang, “A sufficient condition for a balanced bipartite digraph to be hamiltonian”, Discrete Mathematics and Theoretical Computer Science, vol. 19, no. 3, no. 11, 2017.
S.Kh. Darbinyan, “Sufficient conditions for hamiltonian cycles in bipartite digraphs”, Discrete Applied Mathematics, vol. 258, pp. 87-96, 2019.
S.Kh. Darbinyan, “Sufficient conditions for a balanced bipartite digraph to be even pancyclic”, Discrete Applied Mathematics, vol. 238, pp. 70-76, 2018.
J. Adamus, “A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs”, Graphs and Combinatorics, vol. 34, no. 4, pp. 703-709, 2018.
S.Kh. Darbinyan and I.A. Karapetyan, “A sufficient condition for pre-hamiltonian cycles in bipartite digraphs”, ”2017 Computer Science and Information Technologies (CSIT)”, Yerevan, doi:10.1109/CSITechnol. 2017.8312150, pp. 101-109, 2017.
S.Kh. Darbinyan, “On pancyclic digraphs”, Preprint of the Computing Center of Akademy Nauk Armyan. SSR, 21 pp.,1979.
A. Benhocine, “Pancyclism and Meyniel’s conditions”, Discrete Mathematics, vol. 58, pp. 113-120, 1986.
R. Wang and L. Wu, “A dominating pair condition for a balanced bipartite digraph to be hamiltonian”, Australas. J. Combin. vol. 77, no. 1, pp. 136-143, 2020.
J. Adamus, “On dominating pair degree conditions for hamiltonicity in balanced bipartite digraphs”, Discrete Mathematics, vol. 344, no.3, Article 112240, 2021.
R. Wang, “Extremal digraphs on Woodall-type condition for hamiltonian cycles in balanced bipartite digraphs”, Journal of Graph Theory, https://doi.org/10.1002/jgt.22649, 25 November, 2020.
R. Wang, L. Wu and W. Meng, “Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs”, arXiv:1910.05542v1.
S.Kh. Darbinyan, “On hamiltonian bypasses with the condition of Y. Manoussakis”, ”2015 Computer Science and Information Technologies (CSIT)” Yerevan, doi:10.1109/CSITtechnol.2015.7358250 pp. 53-63, 2015.
R. Wang, J. Chang and L. Wu, “A dominated pair condition for a digraph to be hamiltonian”, Discrete Mathematics, vol. 343, no. 5, 111794, 2020.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
