Article in volume
Authors:
Title:
The directed uniform Hamilton-Waterloo Problem involving even cycle sizes
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 615-636
Received: 2023-06-20 , Revised: 2024-04-26 , Accepted: 2024-04-26 , Available online: 2024-06-20 , https://doi.org/10.7151/dmgt.2549
Abstract:
In this paper, factorizations of the complete symmetric digraph $K_v^*$ into
uniform factors consisting of directed even cycle factors are studied as a
generalization of the undirected Hamilton-Waterloo Problem. It is shown, with
a few possible exceptions, that $K_v^*$ can be factorized into two nonisomorphic
factors, where these factors are uniform factors of $K_v^*$ involving $K_2^*$
or directed $m$-cycles, and directed $m$-cycles or $2m$-cycles for even $m$.
Keywords:
The Directed Hamilton-Waterloo Problem, $2$-factorizations, directed cycle factorizations
References:
- R.J.R. Abel, F.E. Bennett and G. Ge, Resolvable perfect Mendelsohn designs with block size five, Discrete Math. 247 (2002) 1–12.
https://doi.org/10.1016/S0012-365X(01)00157-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.
https://doi.org/10.1007/s003730200001 - P. Adams and D. Bryant, Resolvable directed cycle systems of all indices for cycle length $3$ and $4$, unpublished.
- B. Alspach and R. Häggkvist, Some observations on the Oberwolfach problem, J. Graph Theory 9 (1985) 177–187.
https://doi.org/10.1002/jgt.3190090114 - B. Alspach, P.J. Schellenberg, D.R. Stinson and D. Wagner, The Oberwolfach problem and factors of uniform odd length cycles, J. Combin. Theory Ser. A 52 (1989) 20–43.
https://doi.org/10.1016/0097-3165(89)90059-9 - J. Asplund, D. Kamin, M. Keranen, A. Pastine and S. Özkan, On the Hamilton-Waterloo problem with triangle factors and $C_{3x}$-factors, Australas. J. Combin. 64 (2016) 458–474.
- F.E. Bennett and X. Zhang, Resolvable Mendelsohn designs with block size $4$, Aequationes Math. 40 (1990) 248–260.
https://doi.org/10.1007/BF02112298 - F.E. Bennett, R. Wei and L. Zhu., Resolvable Mendelsohn triple systems with equal sized holes, J. Combin. Des. 5 (1997) 329–340.
https://doi.org/10.1002/(SICI)1520-6610(1997)5:5<329::AID-JCD2>3.0.CO;2-H - J.C. Bermond, A. Germa and D. Sotteau, Resolvable decomposition of $K_{n}^{*}$, J. Combin. Theory Ser. A 26 (1979) 179–185.
https://doi.org/10.1016/0097-3165(79)90067-0 - D. Bryant and P. Danziger, On bipartite $2$-factorizations of $K_n-I$ and the Oberwolfach problem, J. Graph Theory 68 (2011) 22–37.
https://doi.org/10.1002/jgt.20538 - D. Bryant, P. Danziger and M. Dean, On the Hamilton-Waterloo problem for bipartite $2$-factors, J. Combin. Des. 21 (2013) 60–80.
https://doi.org/10.1002/jcd.21312 - A.C. Burgess, P. Danziger, A. Pastine and T. Traetta, Constructing uniform $2$-factorizations via row-sum matrices: Solutions to the Hamilton-Waterloo problem, J. Combin. Theory Ser. A 201 (2024) 105803.
https://doi.org/10.1016/j.jcta.2023.105803 - A.C. Burgess, P. Danziger and T. Traetta, On the Hamilton-Waterloo problem with cycle lengths of distinct parities, Discrete Math. 341 (2018) 1636–1644.
https://doi.org/10.1016/j.disc.2018.02.020 - A.C. Burgess, P. Danziger and T. Traetta, The Hamilton-Waterloo problem with even cycle lengths, Discrete Math. 342 (2019) 2213–2222.
https://doi.org/10.1016/j.disc.2019.04.013 - A.C. Burgess, P. Danziger and T. Traetta, On the Hamilton-Waterloo problem with odd cycle lengths, J. Combin. Des. 26 (2018) 51–83.
https://doi.org/10.1002/jcd.21586 - A.C. Burgess, P. Danziger and T. Traetta, On the Hamilton-Waterloo problem with odd orders, J. Combin. Des. 25 (2017) 258–287.
https://doi.org/10.1002/jcd.21552 - A.C. Burgess, N. Francetić and M. Šajna, On the directed Oberwolfach problem with equal cycle lengths: the odd case, Australas. J. Combin. 71 (2018) 272–292.
- A.C. Burgess and M. Šajna, On the directed Oberwolfach problem with equal cycle lengths, Electron. J. Combin. 21 (2014) #P1.15.
https://doi.org/10.37236/2982 - N. Francetić and M. Šajna, On the directed Oberwolfach problem for complete symmetric equipartite digraphs and uniform-length cycles, J. Combin. Des. 31 (2023) 604–641.
https://doi.org/10.1002/jcd.21913 - H. \textcolor{red}{Lei} and H. Shen, The Hamilton-Waterloo problem for Hamilton cycles and triangle-factors, J. Combin. Des. 20 (2012) 305–316.
https://doi.org/10.1002/jcd.20311 - S. Glock, F. Joos, J. Kim, D. Kühn and D. Osthus, Resolution of the Oberwolfach problem, J. Eur. Math. Soc. JEMS 23 (2021) 2511–2547.
https://doi.org/10.4171/jems/1060 - R. Häggkvist, A lemma on cycle decompositions, North-Holland Math. Stud. 115 (1985) 227–232.
https://doi.org/10.1016/S0304-0208(08)73015-9 - D.G. Hoffman and C.A. Rodger, The chromatic index of complete multipartite graphs, J. Graph Theory 16 (1992) 159–163.
https://doi.org/10.1002/jgt.3190160207 - D.G. Hoffman and P.J. Schellenberg, The existence of $C_k$-factorizations of $K_{2n}-F$, Discrete Math. 97 (1991) 243–250.
https://doi.org/10.1016/0012-365X(91)90440-D - M.S. Keranen and S. Özkan, The Hamilton-Waterloo problem with $4$-cycles and a single factor of $n$-cycles, Graphs Combin. 29 (2013) 1827–1837.
https://doi.org/10.1007/s00373-012-1231-6 - A. Lacaze-Masmonteil, Completing the solution of the directed Oberwolfach problem with cycles of equal length, J. Combin. Des. 32 (2024) 5–30.
https://doi.org/10.1002/jcd.21918 - J. Liu, The equipartite Oberwolfach problem with uniform tables, J. Combin. Theory Ser. A 101 (2003) 20–34.
https://doi.org/10.1016/S0097-3165(02)00011-0 - E. Lucas, Récréations Mathématiques vol. 2 (Gauthier-Villars, Paris, 1892).
- U. Odabaş{\i} and S. Özkan, The Hamilton-Waterloo problem with $C_{4}$ and $C_{m}$ factors, Discrete Math. 339 (2016) 263–269.
https://doi.org/10.1016/j.disc.2015.08.013 - U. Odabaş{\i}, Factorizations of complete graphs into cycles and $1$-factors, Contrib. Discrete Math. 15 (2020) 80–89.
https://doi.org/10.11575/cdm.v15i1.62603 - D.K. Ray-Chaudhuri and R.M. Wilson, Solution of Kirkman's schoolgirl problem, in: Proc. Symp. Pure Math., S. Motzkin (Ed(s)), Amer. Math. Soc. 19, (Providence, Rhote Island, 1971) 187–204.
https://doi.org/10.1090/pspum/019/9959 - M. Reiss, Ueber eine Steinersche combinatorische Aufgabe welche im $45^{sten}$ Bande dieses Journals, Seite $181,$ gestellt worden ist., in: Journal für die reine und angewandte Mathematik, Band 56 (1859) 326–344.
https://doi.org/10.1515/9783112368688-029 - T.W. Tillson, A Hamiltonian decomposition of $K_{2m}^*$, $2m\geq8$, J. Combin. Theory Ser. B 29 (1980) 69–74.
https://doi.org/10.1016/0095-8956(80)90044-1 - T. Traetta, A constructive solution to the Oberwolfach problem with a large cycle, Discrete Math. 347 (2024) 113947.
https://doi.org/10.1016/j.disc.2024.113947 - F. Yetgin, U. Odabaş{\i} and S. Özkan, On the directed Hamilton-Waterloo problem with two cycle sizes, Contrib. Discrete Math. (2023) accepted.
Close