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

Degree Sum Condition for Vertex-Disjoint 5-Cycles

Published Online: 27 May 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Aug 2021
Accepted: 02 May 2022
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Let n and k be two integers and G a graph with n = 5k vertices. Wang proved that if δ (G) ≥ 3k, then G contains k vertex disjoint cycles of length 5. In 2018, Chiba and Yamashita asked whether the degree condition can be replaced by degree sum condition. In this paper, we give a positive answer to this question.

Keywords

MSC 2010

[1] S. Abbasi, The Solution of the El-Zahar Problem (PhD Thesis, Rutgers University, 1998). Search in Google Scholar

[2] K. Corrádi and A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math. Acad. Sci. Hungar. 14 (1963) 423–439. https://doi.org/10.1007/BF0189572710.1007/BF01895727 Search in Google Scholar

[3] S. Chiba and T. Yamashita, Degree conditions for the existence of vertex-disjoint cycles and paths: A survey, Graphs Combin. 34 (2018) 1–83. https://doi.org/10.1007/s00373-017-1873-510.1007/s00373-017-1873-5 Search in Google Scholar

[4] G.A. Dirac, Some theorems on abstract graphs, Proc. Lond. Math. Soc. (3) s3-2 (1952) 69–81. https://doi.org/10.1112/plms/s3-2.1.6910.1112/plms/s3-2.1.69 Search in Google Scholar

[5] M.H. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227–230. https://doi.org/10.1016/0012-365X(84)90050-510.1016/0012-365X(84)90050-5 Search in Google Scholar

[6] P. Erdős, Some Recent Combinatorial Problems (Technical Report, University of Bielefeld, 1990). Search in Google Scholar

[7] H. Wang, Proof of the Erdős-Faudree conjecture on quadrilaterals, Graphs Combin. 26 (2010) 833–877. https://doi.org/10.1007/s00373-010-0948-310.1007/s00373-010-0948-3 Search in Google Scholar

[8] H. Wang, Disjoint 5-cycles in a graph, Discuss. Math. Graph Theory 32 (2012) 221–242. https://doi.org/10.7151/dmgt.160510.7151/dmgt.1605 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo