Article in volume
Authors:
Title:
Degree sum condition for vertex-disjoint 5-cycles
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 555-574
Received: 2021-08-01 , Revised: 2022-05-01 , Accepted: 2022-05-02 , Available online: 2022-05-16 , https://doi.org/10.7151/dmgt.2458
Abstract:
Let $n$ and $k$ be two integers and $G$ a graph with $n=5k$ vertices. Wang
proved that if $\delta(G)\geq 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:
degree sum conditions; vertex disjoint 5-cycles
References:
- S. Abbasi, The Solution of the El-Zahar Problem (PhD Thesis, Rutgers University, 1998).
- 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/BF01895727 - 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-5 - 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.69 - M.H. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227–230.
https://doi.org/10.1016/0012-365X(84)90050-5 - P. Erdős, Some Recent Combinatorial Problems (Technical Report, University of Bielefeld, 1990).
- 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-3 - H. Wang, Disjoint $5$-cycles in a graph, Discuss. Math. Graph Theory 32 (2012) 221–242.
https://doi.org/10.7151/dmgt.1605
Close