Geodesic
Cycles of many lengths in balanced bipartite digraphs on dominating and dominated degree conditions
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 245-267 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 lt; 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)≥ 3a-k(l) for every pair of dominating or dominated vertices {u, v}.
Keywords: bipartite digraph, degree sum, bipancyclicity, hamiltonian cycle 
@article{DMGT_2024_44_1_a11,
     author = {Wang, Ruixia and Wu, Linxin},
     title = {Cycles of many lengths in balanced bipartite digraphs on dominating and dominated degree conditions},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {245--267},
     year = {2024},
     volume = {44},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a11/}
}
TY  - JOUR
AU  - Wang, Ruixia
AU  - Wu, Linxin
TI  - Cycles of many lengths in balanced bipartite digraphs on dominating and dominated degree conditions
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 245
EP  - 267
VL  - 44
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a11/
LA  - en
ID  - DMGT_2024_44_1_a11
ER  - 
%0 Journal Article
%A Wang, Ruixia
%A Wu, Linxin
%T Cycles of many lengths in balanced bipartite digraphs on dominating and dominated degree conditions
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 245-267
%V 44
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a11/
%G en
%F DMGT_2024_44_1_a11
Wang, Ruixia; Wu, Linxin. Cycles of many lengths in balanced bipartite digraphs on dominating and dominated degree conditions. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 1, pp. 245-267. http://geodesic.mathdoc.fr/item/DMGT_2024_44_1_a11/

[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.032

[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.1264

[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-6

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

[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.112240

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

[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:23.0.CO;2-J

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

[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.013

[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.024

[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.

[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/BF02122681

[13] M. Meszka, New sufficient conditions for bipancyclicity of balanced bipartite digraphs, Discrete Math. 341 (2018) 3237–3240. https://doi.org/10.1016/j.disc.2018.08.004

[14] M. Meyniel, Une condition suffisante 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-9

[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-4

[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.111794

[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.

[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.22649

[19] R. Wang, A note on dominating pair degree condition for hamiltonian cycles in balanced bipartite digraphs, Graphs Combin.} (2021), accepted.

[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

[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.739