Abstract
A generalization of the Oberwolfach problem, proposed by Liu (J Comb Des 8:42–49, 2000), asks for a uniform 2-factorization of the complete multipartite graph \(K_{m\times n}\). Here we focus our attention on cyclic 2-factorizations, whose 2-factors are disjoint union of cycles all of even length \(\ell \). In particular, we present a complete solution for the extremal cases \(\ell =4\) and \(\ell =mn\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bryant, D., Danziger, P., Dean, M.: On the Hamiltonian–Waterloo problem for bipartite 2-factors. J. Comb. Des. 21, 60–80 (2013)
Bryant, D., Danziger, P., Pettersson, W.: Bipartite 2-factorizations of complete multipartite graphs. J. Graph Theory 78, 287–294 (2015)
Buratti, M.: Abelian 1-factorizations of the complete graph. Eur. J. Comb. 22, 291–295 (2001)
Buratti, M.: Rotational \(k\)-cycle systems of order \(v<3h\); another proof of the existence of odd cycle systems. J. Comb. Des. 11, 433–441 (2003)
Buratti, M., Del Fra, A.: Cyclic hamiltonian cycle systems of the complete graph. Discret. Math. 279, 107–119 (2004)
Buratti, M., Rinaldi, G.: On sharply vertex transitive 2-factorizations of the complete graph. J. Comb. Theory A 111, 245–256 (2005)
Cavenagh, N., El-Zanati, S., Khodkar, A., Vanden Eynden, C.: On a generalization of the Oberwolfach problem. J. Comb. Theory A 106, 255–275 (2004)
El-Zanati, S., Tipnis, S.K., Vanden Eynden, C.: A generalization of the Oberwolfach problem. J. Graph Theory 41, 151–161 (2002)
Gvozdjak, P.: On the Oberwolfach problem for complete multigraphs. Discret. Math. 173, 61–69 (1997)
Jordon, H., Morris, J.: Cyclic hamiltonian cycle systems of the complete graph minus 1-factor. Discret. Math. 308, 2440–2449 (2008)
Liu, J.: A generalization of the Oberwolfach problem and \(C_t\)-factorizations of complete equipartite graphs. J. Comb. Des. 8, 42–49 (2000)
Liu, J.: The equipartite Oberwolfach problem with uniform tables. J. Comb. Theory A 101, 20–34 (2003)
Liu, J., Lick, D.R.: On \(\lambda \)-fold equipartite Oberwolfach problem with uniform table sizes. Ann. Comb. 7, 315–323 (2003)
Mazzuoccolo, G.: Primitive 2-factorizations of the complete graph. Discret. Math. 308, 175–179 (2008)
Merola, F., Pasotti, A., Pellegrini, M.A.: Cyclic and symmetric hamiltonian cycle systems of the complete multipartite graph: even number of parts. ARS Math. Contemp. 12, 219–233 (2017)
Ollis, M.A., Preece, D.A.: Sectionable terraces and the (generalised) Oberwolfach problem. Discret. Math. 266, 399–416 (2003)
Pasotti, A., Pellegrini, M.A.: Symmetric 1-factorizations of the complete graph. Eur. J. Comb. 31, 1410–1418 (2010)
Piotrowski, W.: The solution of the bipartite analogue of the Oberwolfach problem. Discret. Math. 97, 339–356 (1991)
Rinaldi, G.: Nilpotent 1-factorizations of the complete graph. J. Comb. Des. 13, 393–405 (2005)
Traetta, T.: A complete solution to the two-table Oberwolfach problems. J. Comb. Theory Ser. A 120, 984–997 (2013)
Acknowledgements
The authors would like to thank Francesca Merola for the interesting discussions and for her suggestions about the hamiltonian case.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Pasotti, A., Pellegrini, M.A. Cyclic Uniform 2-Factorizations of the Complete Multipartite Graph. Graphs and Combinatorics 34, 901–930 (2018). https://doi.org/10.1007/s00373-018-1920-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-018-1920-x