DMGT

Disjoint 5-cycles in a Graph

Hong Wang

Department of Mathematics
The University of Idaho
Moscow, Idaho, 83844 USA

We prove that if G is a graph of order 5k and the minimum degree of G is at least 3k then G contains k disjoint cycles of length 5.

Keywords: 5-cycles, pentagons, cycles, cycle coverings

2010 Mathematics Subject Classification: 05C38, 05C70, 05C75.

[1]	S. Abbasi, PhD Thesis (Rutgers University 1998).
[2]	B. Bollobás, Extremal Graph Theory ( Academic Press, London, 1978).
[3]	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, doi: 10.1007/BF01895727.
[4]	M.H. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227--230, doi: 10.1016/0012-365X(84)90050-5.
[5]	P. Erdös, Some recent combinatorial problems, Technical Report, University of Bielefeld, Nov. 1990.
[6]	B. Randerath, I. Schiermeyer and H. Wang, On quadrilaterals in a graph, Discrete Math. 203 (1999) 229--237, doi: 10.1016/S0012-365X(99)00053-9.
[7]	H. Wang, On quadrilaterals in a graph, Discrete Math. 288 (2004) 149--166, doi: 10.1016/j.disc.2004.02.020.
[8]	H. Wang, Proof of the Erdös-Faudree conjecture on quadrilaterals, Graphs and Combin. 26 (2010) 833--877, doi: 10.1007/s00373-010-0948-3.

Received 26 October 2010
Revised 17 April 2011
Accepted 17 April 2011