1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Cycles of Many Lengths in Balanced Bipartite Digraphs on Dominating and Dominated Degree Conditions

Published Online: 10 Jan 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 15 Jul 2021
Accepted: 29 Nov 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

In 2017, Adamus proved that a strong balanced bipartite digraph of order 2a with a ≥ 3 is hamiltonian, if d(u) + d(v) ≥ 3a for every pair of dominating or dominated vertices {u, v}. In this paper, we characterize all non-hamiltonian bipartite digraphs when d(u) + d(v) ≥ 3a − 1 for every pair of dominating or dominated vertices {u, v}, consisting of one infinite family and four exceptional bipartite digraphs of order six. Using this result, we also prove that a strong balanced bipartite digraph of order 2a with a ≥ 4 contains all cycles of lengths 2, 4, . . ., 2a − 2 except for a single bipartite digraph, and also contains a hamiltonian path, if d(u) + d(v) ≥ 3a − 1 for every pair of dominating or dominated vertices {u, v}. The bounds for 3a−1 in two results are sharp. This partly settles the following problem when l = a−1 proposed by Adamus [A Meyniel-type condition for bipancyclicity in balanced bipartitie digraphs, Graphs Combin. 34 (2018) 703–709]. Whether for every 1 ≤ l < a there is a k(l), k(l) ≥ 1, such that every strong balanced bipartite digraph of order 2a contains cycles of lengths 2, 4, . . ., 2l, whenever d(u) + d(v) ≥ 3ak(l) for every pair of dominating or dominated vertices {u, v}.

Keywords

MSC 2010

[1] J. Adamus and L. Adamus, A degree condition for cycles of maximum length in bipartite digraphs, Discrete Math. 312 (2012) 1117–1122. https://doi.org/10.1016/j.disc.2011.11.03210.1016/j.disc.2011.11.032 Search in Google Scholar

[2] J. Adamus, L. Adamus, and A. Yeo, On the Meyniel condition for hamiltonicity in bipartite digraphs, Discrete Math. Theor. Comput. Sci. 16 (2014) 293–302. https://doi.org/10.46298/dmtcs.126410.46298/dmtcs.1264 Search in Google Scholar

[3] J. Adamus, A degree sum condition for hamiltonicity in balanced bipartite digraphs, Graphs Combin. 33 (2017) 43–51. https://doi.org/10.1007/s00373-016-1751-610.1007/s00373-016-1751-6 Search in Google Scholar

[4] J. Adamus, A Meyniel-type condition for bipancyclicity in balanced bipartitie di-graphs, Graphs Combin. 34 (2018) 703–709. https://doi.org/10.1007/s00373-018-1907-710.1007/s00373-018-1907-7 Search in Google Scholar

[5] J. Adamus, On dominating pair degree conditions for hamiltonicity in balanced bipartite digraphs, Discrete Math. 344 (2021) 112240. https://doi.org/10.1016/j.disc.2020.11224010.1016/j.disc.2020.112240 Search in Google Scholar

[6] D. Amar and Y. Manoussakis, Cycles and paths of many lengths in bipartite di-graphs, J. Combin. Theory Ser. B 50 (1990) 254–264. https://doi.org/10.1016/0095-8956(90)90081-A10.1016/0095-8956(90)90081-A Search in Google Scholar

[7] J. Bang-Jensen, G. Gutin and H. Li, Sufficient conditions for a digraph to be Hamiltonian, J. Graph Theory 22(2) (1996) 181–187. https://doi.org/10.1002/(SICI)1097-0118(199606)22:2¡181::AID-JGT9¿3.0.CO;2-J Search in Google Scholar

[8] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000). https://doi.org/10.1007/978-1-4471-3886-010.1007/978-1-4471-3886-0 Search in Google Scholar

[9] S.Kh. Darbinyan, Sufficient conditions for a balanced bipartite digraph to be even pancyclic, Discrete Appl. Math. 238 (2018) 70–76. https://doi.org/10.1016/j.dam.2017.12.01310.1016/j.dam.2017.12.013 Search in Google Scholar

[10] S.Kh. Darbinyan, Sufficient conditions for Hamiltonian cycles in bipartite digraphs, Discrete Appl. Math. 258 (2019) 87–96. https://doi.org/10.1016/j.dam.2018.11.02410.1016/j.dam.2018.11.024 Search in Google Scholar

[11] G. Gutin, Criterion for complete bipartite digraphs to be Hamiltonian, Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk 1 (1984) 109–110, in Russian. Search in Google Scholar

[12] R. Häggkvist and Y. Manoussakis, Cycles and paths in bipartite tournaments with spanning configurations, Combinatorica 9 (1989) 33–38. https://doi.org/10.1007/BF0212268110.1007/BF02122681 Search in Google Scholar

[13] M. Meszka, New sufficient conditions for bipancyclicity of balanced bipartite di-graphs, Discrete Math. 341 (2018) 3237–3240. https://doi.org/10.1016/j.disc.2018.08.00410.1016/j.disc.2018.08.004 Search in Google Scholar

[14] M. Meyniel, Une condition su sante d’existence d’un circuit hamiltonien dans un graphe orienté, J. Combin. Theory Ser. B 14 (1973) 137–147. https://doi.org/10.1016/0095-8956(73)90057-910.1016/0095-8956(73)90057-9 Search in Google Scholar

[15] C. Thomassen, An Ore-type condition implying a digraph to be pancyclic, Discrete Math. 19 (1977) 85–92. https://doi.org/10.1016/0012-365X(77)90122-410.1016/0012-365X(77)90122-4 Search in Google Scholar

[16] R. Wang, J. Chang and L. Wu, A dominated pair condition for a digraph to be hamiltonian, Discrete Math. 343 (2020) 111794. https://doi.org/10.1016/j.disc.2019.11179410.1016/j.disc.2019.111794 Search in Google Scholar

[17] R. Wang and L. Wu, A dominating pair condition for a balanced bipartite digraph to be hamiltonian, Australas. J. Combin. 77 (2020) 136–143. Search in Google Scholar

[18] R. Wang, Extremal digraphs on Woodall-type condition for hamiltonian cycles in balanced bipartite digraphs, J. Graph Theory 97 (2021) 194–207. https://doi.org/10.1002/jgt.2264910.1002/jgt.22649 Search in Google Scholar

[19] R. Wang, A note on dominating pair degree condition for hamiltonian cycles in balanced bipartite digraphs, Graphs Combin. (2021), accepted.10.1007/s00373-021-02404-8 Search in Google Scholar

[20] R. Wang, A sufficient condition for a balanced bipartite digraph to be hamiltonian, Discrete Math. Theor. Comput. Sci. 19(3) (2017) #11. https://doi.org/https://doi.org/10.23638/DMTCS-19-3-11 Search in Google Scholar

[21] D.R. Woodall, Sufficient conditions for circuits in graphs, Proc. Lond. Math. Soc. (3) 24 (1972) 739–755. https://doi.org/10.1112/plms/s3-24.4.73910.1112/plms/s3-24.4.739 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo