In this paper, a sufficient condition for a balanced bipartite graph to contain a 2-factor F is given. We show that every balanced bipartite graph of order 2n
and
contains a 2-factor with k components,
-cycle,
,
-cycle, if one of the following is satisfied: (1)
,
and
; (2)
,
and
. In particular, this extends one result of Moon and Moser in 1963 under condition (1).
References
[1]
Dirac, G.A. (1952) Some Theorems on Abstract Graphs. Proceedings of the London Mathematical Society, 3, 69-81. https://doi.org/10.1112/plms/s3-2.1.69
[2]
Erdős, P. and Gallai, T. (1959) On Maximal Paths and Circuits of Graphs. Acta Mathematica AcademiaeScientiarumHungaricae, 10, 337-356. https://doi.org/10.1007/bf02024498
[3]
Ore, O. (1960) Note on Hamilton Circuits. The American Mathematical Monthly, 67, 55. https://doi.org/10.2307/2308928
[4]
Brandt, S., Chen, G., Faudree, R., Gould, R.J. and Lesniak, L. (1997) Degree Conditions for 2-Factors. Journal of Graph Theory, 24, 165-173. https://doi.org/10.1002/(sici)1097-0118(199702)24:2<165::aid-jgt4>3.0.co;2-o
[5]
Moon, J. and Moser, L. (1963) On Hamiltonian Bipartite Graphs. Israel Journal of Mathematics, 1, 163-165. https://doi.org/10.1007/bf02759704
[6]
Wang, H. (1999) On 2-Factors of a Bipartite Graph. Journal of Graph Theory, 31, 101-106. https://doi.org/10.1002/(sici)1097-0118(199906)31:2<101::aid-jgt3>3.3.co;2-x
[7]
Chen, G., Faudree, R.J., Gould, R.J., Jacobson, M.S. and Lesniak, L. (2000) Cycles in 2-Factors of Balanced Bipartite Graphs. Graphs and Combinatorics, 16, 67-80. https://doi.org/10.1007/s003730050004
[8]
Li, X., Wei, B. and Yang, F. (2001) A Degree Condition of 2-Factors in Bipartite Graphs. Discrete Applied Mathematics, 113, 311-318. https://doi.org/10.1016/s0166-218x(00)00380-2
[9]
Chiba, S. and Yamashita, T. (2017) A Note on Degree Sum Conditions for 2-Factors with a Prescribed Number of Cycles in Bipartite Graphs. Discrete Mathematics, 340, 2871-2877. https://doi.org/10.1016/j.disc.2017.07.028
[10]
Zhang, X., Jiang, Z. and Zhang, X. (2024) Polychromatic Edge-Colorings of Subgraphs of Balanced Complete Bipartite Graphs. Scientia Sinica Mathematica, 54, 1889-1904. https://doi.org/10.1360/ssm-2023-0254