207Accesses
12Citations
Abstract
The main result of this paper is the explicit construction, for any positive integern, of a cyclic two-factorization of\(K_{50n+5}\) with\(20n+2\) two-factors consisting of five\((10n+1)\)-cycles and each of the remaining two-factors consisting of all pentagons. Then, applying suitable composition constructions, we obtain a few other two-factorizations also having two-factors of two distinct types.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.References
Abel, R.J.R., Ge, G., Yin, J.: Resolvable and near-resolvable designs. In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, 2nd edn, pp. 740–754. CRC Press, Boca Raton (2007)
Abel, R.J.R., Colbourn, C.J., Dinitz, J.H.: Mutually orthogonal latin squares (MOLS). In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, 2nd edn, pp. 740–754. CRC Press, Boca Raton (2007)
Adams, P., Bryant, D.: Two-factorisations of complete graphs of orders fifteen and seventeen. Australas. J. Combin.35, 113–118 (2006)
Adams, P., Billington, E.J., Bryant, D., El-Zanati, S.I.: On the Hamilton–Waterloo problem. Graphs Combin.18, 31–51 (2002)
Anderson, L.D.: Factorizations of graphs. In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, 2nd edn, pp. 740–754. CRC Press, Boca Raton (2007)
Bryant, D., Danziger, P., Pettersson, W.: Bipartite\(2\)-factorizations of complete multipartite graphs. J. Graph Theory78(4), 287–294 (2015)
Bonvicini, S., Buratti, M.: Sharply vertex transitive 2-factorizations of Cayley graphs (preprint)
Bryant, D., Danziger, P.: On bipartite\(2\)-factorizations of\(K_n - I\) and the Oberwolfach problem. J. Graph Theory68, 22–37 (2011)
Bryant, D., Rodger, C.: Cycle decompositions. In: Colbourn, C.J., Dinitz, J.H. (eds.) The CRC Handbook of Combinatorial Designs, 2nd edn, pp. 373–382. CRC Press, Boca Raton (2007)
Bryant, D., Scharaschkin, V.: Complete solutions to the Oberwolfach problem for an infinite set of orders. J. Combin. Theory Ser. B99, 904–918 (2009)
Buratti, M., Del Fra, A.: Cyclic Hamiltonian cycle systems of the complete graph. Discrete Math.279, 107–119 (2004)
Buratti, M., Rania, F., Zuanni, F.: Some constructions for cyclic perfect cycle systems. Discrete Math.299, 33–48 (2005)
Buratti, M., Rinaldi, G.: On sharply vertex transitive\(2\)-factorizations of the complete graph. J. Combin. Theory Ser. A111, 245–256 (2005)
Buratti, M., Rinaldi, G.:\(1\)-rotational\(k\)-factorizations of the complete graph and new solutions to the Oberwolfach problem. J. Combin. Des.16, 87–100 (2008)
Danziger, P., Quattrocchi, G., Stevens, B.: The Hamilton-Waterloo problem for cycle sizes 3 and 4. J. Combin. Des.17, 342–352 (2009)
Deza, A., Franek, F., Hua, W., Meszka, M., Rosa, A.: Solutions to the Oberwolfach problem for orders\(18\) to\(40\). JCMCC74, 95–102 (2010)
Dinitz, J.H., Ling, A.: The Hamilton-Waterloo problem: the case of triangle-factors and one Hamilton cycle. J. Combin. Des.17, 160–176 (2009)
Dinitz, J.H., Ling, A.C.H.: The Hamilton-Waterloo problem: The case of triangle-factors and Hamilton cycles: The case\(n\equiv 3~(\text{ mod } \;\;\; 18)\). J. Combin. Math. Combin. Comput.70, 143–147 (2009)
Franek, F., Holub, J., Rosa, A.: Two-factorizations of small complete graphs. II. The case of 13 vertices. J. Combin. Math. Combin. Comput.51, 89–94 (2004)
Franek, F., Rosa, A.: Two-factorizations of small complete graphs. J. Stat. Plann. Inference86, 435–442 (2000)
Horak, P., Nedela, R., Rosa, A.: The Hamilton–Waterloo problem: the case of Hamilton cycles and triangle-factors. Discrete Math.284, 181–188 (2004)
Jordon, H., Morris, J.: Cyclic hamiltonian cycle systems of the complete graph minus a\(1\)-factor. Discrete Math.308, 2440–2449 (2008)
Keranen, M.S., Ozkan, S.: The Hamilton–Waterloo Problem with 4-cycles and a single factor of\(n\)-cycles. Graphs Combin.29, 1827–1837 (2013)
Liu, J.: The equipartite Oberwolfach problem with uniform tables. J. Combin. Theory Ser. A101, 20–34 (2003)
Liu, J., Lick, D.R.: On\(\lambda \)-fold equipartite Oberwolfach problem with uniform table sizes. Ann. Comb.7, 315–323 (2003)
Piotrowski, W.L.: The solution of the bipartite analogue of the Oberwolfach problem. Discrete Math.97, 339–356 (1991)
Rinaldi, G., Traetta, T.: Graph products and new solutions to Oberwolfach problems. Electron. J. Combin.18, P52 (2011)
Shalaby, N.: Skolem and Langford sequences. In: Colbourn, C.J., Dinitz, J.H. (eds.) CRC Handbook of Combinatorial Designs, pp. 612–616. CRC Press, Boca Raton (2006)
Traetta, T.: A complete solution to the two-table Oberwolfach problems. J. Combin. Theory Ser. A120, 984–997 (2013)
West, D.: Introduction to Graph Theory. Prentice Hall, New Jersey (1996)
Acknowledgments
M. Buratti is supported by MIUR (project “Disegni combinatori, grafi e loro applicazioni”, PRIN 2008). P. Danziger is supported by the NSERC Discovery program. The bulk of this work was carried out when the second author visited University Sapienza of Rome. The support and hospitality of the department during this visit was greatly appreciated.
Author information
Authors and Affiliations
Dipartimento di Matematica e Informatica, Università di Perugia, via Vanvitelli 1, 06123, Perugia, Italy
Marco Buratti
Department of Mathematics, Ryerson University, 350 Victoria Street, Toronto, ON, M5B 2K3, Canada
Peter Danziger
- Marco Buratti
Search author on:PubMed Google Scholar
- Peter Danziger
Search author on:PubMed Google Scholar
Corresponding author
Correspondence toMarco Buratti.
Rights and permissions
About this article
Cite this article
Buratti, M., Danziger, P. A Cyclic Solution for an Infinite Class of Hamilton–Waterloo Problems.Graphs and Combinatorics32, 521–531 (2016). https://doi.org/10.1007/s00373-015-1582-x
Received:
Revised:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative