Article in volume
Authors:
Title:
Cycles of many lengths in balanced bipartite digraphs on dominating and dominated degree conditions
PDFSource:
Discussiones Mathematicae Graph Theory 44(1) (2024) 245-267
Received: 2021-07-15 , Revised: 2021-11-29 , Accepted: 2021-11-29 , Available online: 2021-12-14 , https://doi.org/10.7151/dmgt.2442
Abstract:
In 2017, Adamus proved that a strong balanced bipartite digraph of order $2a$
with $a\geq 3$ is hamiltonian, if $d(u)+d(v)\geq 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)\geq 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\geq 4$
contains all cycles of lengths $2, 4, \ldots, 2a-2$ except for a single bipartite
digraph, and also contains a hamiltonian path, if $d(u)+d(v)\geq 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\le l< a$ there is a $k(l)$, $k(l)\ge 1$, such that every strong balanced bipartite
digraph of order $2a$ contains cycles of lengths $2, 4, \ldots, 2l$, whenever
$d(u)+d(v)\ge 3a-k(l)$ for every pair of dominating or dominated vertices
$\{u, v\}$.
Keywords:
bipartite digraph, degree sum, bipancyclicity, hamiltonian cycle
References:
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer, London, 2000).
https://doi.org/10.1007/978-1-4471-3886-0 - 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 - 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 - G. Gutin, Criterion for complete bipartite digraphs to be Hamiltonian, Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk 1 (1984) 109–110, in Russian.
- 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 - 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 - 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 - 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 - 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 - R. Wang and L. Wu, A dominating pair condition for a balanced bipartite digraph to be hamiltonian, Australas. J. Combin. 77 (2020) 136–143.
- 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 - R. Wang, A note on dominating pair degree condition for hamiltonian cycles in balanced bipartite digraphs, Graphs Combin. (2021), accepted.
- 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 - 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
Close