Factorizations of complete graphs into cycles and 1-factors





In this paper, we consider factorizations of complete graph $K_v$ into cycles and $1$--factors. We will focus on the existence of factorizations of $K_v$ containing two nonisomorphic factors. We obtain all possible solutions for uniform factors involving $m$--cycles and $1$--factors with a few possible exceptions when $m$ is odd.


[1] P. Adams, E. J. Billington, D. E. Bryant, and S. I. El-Zanati, On the Hamilton-Waterloo problem, Graphs Combin. 18 (2002), 31-51.

[2] P. Adams, D. Bryant, S.I. El-Zanati, H. Gavlas, Factorizations of the complete graphinto C5-factors and 1-factors, Graphs Combin. 19 (2003), 289-296.

[3] B. Alspach, P.J. Schellenberg, D.R. Stinson, Wagner, D., The Oberwolfach problem and factors of uniform odd length cycles. J. Comb. Theory Ser. A 52 (1989), 20-43.

[4] Z. Baranyai, Gy. R. Szasz, Hamiltonian decomposition of lexicographic product, J. Comb. Theory Ser. B 31 (1981), 253 - 261.

[5] J-C. Bermond, O. Favaron, M. Maheo, Hamiltonian decomposition of Cayley graphs of degree 4, J. Comb. Theory Ser. B 46 (1989), 142-153.

[6] S. Bonvicini, M. Buratti, Octahedral, dicyclic and special linear solutions of some Hamilton-Waterloo problems, Ars Math. Contemp. 14 (2018), 1-14.

[7] D. Bryant, P. Danziger and M. Dean, On the Hamilton-Waterloo problem for bipartite 2-factors, J. Combin. Des. 21 (2013), 60-80.

[8] M. Buratti, P. Danziger, A cyclic solution for an infnite class of Hamilton-Waterloo problems, Graphs Combin. 32 (2016), 521 - 531.

[9] M. Buratti, G. Rinaldi, On sharply vertex transitive 2-factorizations of the complete graph, J. Comb. Theory Ser. A 111 (2005), 245 - 256.

[10] A. C. Burgess, P. Danziger, T. Traetta. On the Hamilton-Waterloo problem with odd orders, J. Combin. Des. 25 (2017), 258-287.

[11] A. C. Burgess, P. Danziger, T. Traetta. On the Hamilton-Waterloo problem with cycle lengths of distinct parities, Discrete Math. 341 (2018), 1636-1644.

[12] A. C. Burgess, P. Danziger, T. Traetta. On the Hamilton-Waterloo problem with odd cycle lengths, J. Combin. Des. 26 (2018), 51-83.

[13] N.J. Cavenagh, S.I. El-Zanati, A. Khodkar, C. Vanden Eynden, On a generalization of the Oberwolfach problem, J. Comb. Theory Ser. A 106 (2004), 255-275.

[14] R. Haggkvist, A lemma on cycle decompositions, Ann. Discrete Math. 27 (1985), 227-232.

[15] DG. Ho_man, PJ. Schellenberg, The existence of Ck-factorizations of K2n -I, Discrete Math. 97 (1991), 243-250.

[16] E. Kohler, Uber das Oberwolfacher problem, Beitrage zur Geometrischen Algebra, Basel (1977), 189-201.

[17] J. Liu, The equipartite Oberwolfach problem with uniform tables, J. Combin. Theory Ser. A 101 (2003), 20-34.

[18] E. Lucas, R_ecr_eations math_ematiques, Vol. 2 (1892), Gauthier-Villars, Paris.

[19] U. Odabaşı, S. Özkan, The Hamilton-Waterloo problem with C4 and Cm factors, Discrete Math. 339 (2016), 263-269.

[20] U. Odabaşı, S. Özkan, Uniformly resolvable cycle decompositions with four different factors, Graphs Combin. 33 (2017), 1591-1606.

[21] W. L. Piotrowski, Untersuchungen uber das Oberwolfacher problem. Arbeitspapier (1979).

[22] W. L. Piotrowski, The solution of the bipartite analogue of the Oberwolfach problem, Discrete Math. 97 (1991), 339-356.

[23] R. Rees, Uniformly Resolvable Pairwise balanced designs with block sizes two and three, J. Comb. Theory Ser. A 45 (1987), 207-225.

[24] L. Wang, H. Cao, Completing the spectrum of almost resolvable cycle systems with odd cycle length, Discrete Math. 341 (2018), 1479-1491.

[25] L. Wang, F. Chen, H. Cao, The Hamilton-Waterloo problem for C3-factors and Cn-factors, J. Comb. Des. 25 (2017), 385-418.