全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Engineering  2024 

2-Factors with a Few Components in Balanced Bipartite Graphs

DOI: 10.4236/eng.2024.1611027, PP. 361-370

Keywords: 2-Factor, Bipartite Graph, Degree Condition

Full-Text   Cite this paper   Add to My Lib

Abstract:

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 ( n6 ) and e( G )> n 2 2n+4 contains a 2-factor with k components, 2 d 1 -cycle, , 2 d k -cycle, if one of the following is satisfied: (1) k=2 , δ( G )2 and d 1 2 d 2 2 ; (2) k=3 , δ( G ) d 3 +2 and d 1 2 d 2 d 3 4 . 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 Academiae Scientiarum Hungaricae, 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

Full-Text

Contact Us

[email protected]

QQ:3279437679

WhatsApp +8615387084133