Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Alspach’s Problem: The Case of Hamilton Cycles and 5-Cycles. | Alspach s Problem The Case of Hamilton Cycles and 5-Cycles Heather Jordon Department of Mathematics Illinois State University Normal IL 61790-4520 hj ordon@ Submitted Oct 19 2009 Accepted Mar 26 2011 Published Apr 7 2011 Mathematics Subject Classifications 05C70 05C38 Abstract In this paper we settle Alspach s problem in the case of Hamilton cycles and 5-cycles that is we show that for all odd integers n 5 and all nonnegative integers h and t with hn 5t n n 1 2 the complete graph Kn decomposes into h Hamilton cycles and t 5-cycles and for all even integers n 6 and all nonnegative integers h and t with hn 5t n n 2 2 the complete graph Kn decomposes into h Hamilton cycles t 5-cycles and a 1-factor. We also settle Alspach s problem in the case of Hamilton cycles and 4-cycles. 1 Introduction In 1981 Alspach 5 posed the following problem Prove there exists a decomposition of Kn n odd or Kn I n even into cycles of lengths mi m2 . mt whenever 3 mi n for 1 i t and mi m2 mt n n 1 2 number of edges in Kn or mi m2 mt n n 2 2 the number of edges in Kn I . Results of Alspach Gavlas and Sajna 6 32 settle Alspach s problem in the case that all the cycle lengths are the same . mi m2 mt m. The problem has attracted much interest and has also been settled for several cases in which a small number of short cycle lengths are allowed 3 4 9 25 26 31 . Two surveys are given in 12 18 . In 19 Caro and Yuster settle Alspach s problem for all n N L where L max mi m2 . mt and N L is a function of L which grows faster than exponentially. In 8 Balister improved the result of Caro and Yuster by settling the problem for all n N where N is a very large constant given by a linear function of L and the longest cycle length is less than about 20. In 16 Bryant and Horsley show that there exists a sufficiently large integer N such that for all odd n N the complete graph THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P82 1 Kn decomposes into cycles of lengths m1 m2 . mt with 3 mi n for 1 i
