Movatterモバイル変換


[0]ホーム

URL:


Skip to main content
Springer Nature Link
Log in

A Cyclic Solution for an Infinite Class of Hamilton–Waterloo Problems

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

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

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

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

  1. 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)

    Google Scholar 

  2. 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)

    Google Scholar 

  3. Adams, P., Bryant, D.: Two-factorisations of complete graphs of orders fifteen and seventeen. Australas. J. Combin.35, 113–118 (2006)

    MathSciNet MATH  Google Scholar 

  4. Adams, P., Billington, E.J., Bryant, D., El-Zanati, S.I.: On the Hamilton–Waterloo problem. Graphs Combin.18, 31–51 (2002)

    Article MathSciNet MATH  Google Scholar 

  5. 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)

    Google Scholar 

  6. Bryant, D., Danziger, P., Pettersson, W.: Bipartite\(2\)-factorizations of complete multipartite graphs. J. Graph Theory78(4), 287–294 (2015)

    Article MathSciNet MATH  Google Scholar 

  7. Bonvicini, S., Buratti, M.: Sharply vertex transitive 2-factorizations of Cayley graphs (preprint)

  8. Bryant, D., Danziger, P.: On bipartite\(2\)-factorizations of\(K_n - I\) and the Oberwolfach problem. J. Graph Theory68, 22–37 (2011)

    Article MathSciNet MATH  Google Scholar 

  9. 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)

    Google Scholar 

  10. Bryant, D., Scharaschkin, V.: Complete solutions to the Oberwolfach problem for an infinite set of orders. J. Combin. Theory Ser. B99, 904–918 (2009)

    Article MathSciNet MATH  Google Scholar 

  11. Buratti, M., Del Fra, A.: Cyclic Hamiltonian cycle systems of the complete graph. Discrete Math.279, 107–119 (2004)

    Article MathSciNet MATH  Google Scholar 

  12. Buratti, M., Rania, F., Zuanni, F.: Some constructions for cyclic perfect cycle systems. Discrete Math.299, 33–48 (2005)

    Article MathSciNet MATH  Google Scholar 

  13. Buratti, M., Rinaldi, G.: On sharply vertex transitive\(2\)-factorizations of the complete graph. J. Combin. Theory Ser. A111, 245–256 (2005)

    Article MathSciNet MATH  Google Scholar 

  14. 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)

    Article MathSciNet MATH  Google Scholar 

  15. Danziger, P., Quattrocchi, G., Stevens, B.: The Hamilton-Waterloo problem for cycle sizes 3 and 4. J. Combin. Des.17, 342–352 (2009)

    Article MathSciNet MATH  Google Scholar 

  16. Deza, A., Franek, F., Hua, W., Meszka, M., Rosa, A.: Solutions to the Oberwolfach problem for orders\(18\) to\(40\). JCMCC74, 95–102 (2010)

    MathSciNet MATH  Google Scholar 

  17. 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)

    Article MathSciNet MATH  Google Scholar 

  18. 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)

    MathSciNet MATH  Google Scholar 

  19. 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)

    MathSciNet MATH  Google Scholar 

  20. Franek, F., Rosa, A.: Two-factorizations of small complete graphs. J. Stat. Plann. Inference86, 435–442 (2000)

    Article MathSciNet MATH  Google Scholar 

  21. Horak, P., Nedela, R., Rosa, A.: The Hamilton–Waterloo problem: the case of Hamilton cycles and triangle-factors. Discrete Math.284, 181–188 (2004)

    Article MathSciNet MATH  Google Scholar 

  22. Jordon, H., Morris, J.: Cyclic hamiltonian cycle systems of the complete graph minus a\(1\)-factor. Discrete Math.308, 2440–2449 (2008)

    Article MathSciNet MATH  Google Scholar 

  23. 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)

    Article MathSciNet MATH  Google Scholar 

  24. Liu, J.: The equipartite Oberwolfach problem with uniform tables. J. Combin. Theory Ser. A101, 20–34 (2003)

    Article MathSciNet MATH  Google Scholar 

  25. Liu, J., Lick, D.R.: On\(\lambda \)-fold equipartite Oberwolfach problem with uniform table sizes. Ann. Comb.7, 315–323 (2003)

    Article MathSciNet  Google Scholar 

  26. Piotrowski, W.L.: The solution of the bipartite analogue of the Oberwolfach problem. Discrete Math.97, 339–356 (1991)

    Article MathSciNet MATH  Google Scholar 

  27. Rinaldi, G., Traetta, T.: Graph products and new solutions to Oberwolfach problems. Electron. J. Combin.18, P52 (2011)

    MathSciNet  Google Scholar 

  28. 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)

    Google Scholar 

  29. Traetta, T.: A complete solution to the two-table Oberwolfach problems. J. Combin. Theory Ser. A120, 984–997 (2013)

    Article MathSciNet MATH  Google Scholar 

  30. West, D.: Introduction to Graph Theory. Prentice Hall, New Jersey (1996)

    MATH  Google Scholar 

Download references

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

  1. Dipartimento di Matematica e Informatica, Università di Perugia, via Vanvitelli 1, 06123, Perugia, Italy

    Marco Buratti

  2. Department of Mathematics, Ryerson University, 350 Victoria Street, Toronto, ON, M5B 2K3, Canada

    Peter Danziger

Authors
  1. Marco Buratti
  2. Peter Danziger

Corresponding author

Correspondence toMarco Buratti.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

Keywords

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement


[8]ページ先頭

©2009-2025 Movatter.jp