×

Uniformly resolvable cycle decompositions with four different factors. (English) Zbl 1380.05110

Summary: In this paper, we consider uniformly resolvable decompositions of complete graph \(K_v\) (or \(K_v\) minus a 1-factor \(I\) for even \(v\)) into cycles. We will focus on the existence of factorizations of \(K_v\) or \(K_v-I\) containing up to four non-isomorphic factors. We obtain all possible solutions for uniform factors involving 4, \(m\), \(2m\) and \(4m\)-cycles with a few possible exceptions when \(m\) is odd.

MSC:

05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, P., Billington, E.J., Bryant, D.E., El-Zanati, S.I.: On the Hamilton-Waterloo problem. Graphs Comb. 18, 31-51 (2002) · Zbl 0995.05116 · doi:10.1007/s003730200001
[2] Alspach, B., Schellenberg, P.J., Stinson, D.R., Wagner, D.: The Oberwolfach problem and factors of uniform odd length cycles. J. Comb. Theory Ser. A 52, 20-43 (1989) · Zbl 0684.05035 · doi:10.1016/0097-3165(89)90059-9
[3] Assaf, A., Hartman, A.: Resolvable group divisible designs with block size 3. Discrete Math. 77, 5-20 (1989) · Zbl 0714.05007 · doi:10.1016/0012-365X(89)90346-4
[4] Bryant, D., Danziger, P., Dean, M.: On the Hamilton-Waterloo problem for bipartite 2-factors. J Comb. Des. 21, 60-80 (2013) · Zbl 1260.05117 · doi:10.1002/jcd.21312
[5] Buratti, M., Danziger, P.: A cyclic solution for an infinite class of Hamilton-Waterloo problems. Graphs Comb. 32, 521-531 (2016) · Zbl 1339.05301 · doi:10.1007/s00373-015-1582-x
[6] Buratti, M., Rinaldi, G.: On sharply vertex transitive 2-factorizations of the complete graph. J. Comb. Theory Ser. A 111, 245-256 (2005) · Zbl 1070.05066 · doi:10.1016/j.jcta.2004.11.014
[7] Cavenagh, N.J., El-Zanati, S.I., Khodkar, A., Vanden Eynden, C.: On a generalization of the Oberwolfach problem. J. Comb. Theory Ser. A 106(2), 255-275 (2004) · Zbl 1042.05080 · doi:10.1016/j.jcta.2004.02.003
[8] Danziger, P., Quattrocchi, G., Stevens, B.: The Hamilton-Waterloo problem for cycle sizes 3 and 4. J. Comb. Des. 17, 342-352 (2009) · Zbl 1222.05119 · doi:10.1002/jcd.20219
[9] Diestel, R.: Graph Theory, 4th edn. Springer, Berlin (2010) · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6
[10] Dinitz, J.H., Ling, A.C.H.: The Hamilton-Waterloo problem: the case of triangle-factors and one Hamilton cycle. J. Comb. Des. 17, 160-176 (2009) · Zbl 1204.05074 · doi:10.1002/jcd.20196
[11] Lo Faro, G., Milici, S., Tripodi, A.: Uniformly resolvable decompositions of \[K_v\] Kv into paths on two, three and four vertices. Discrete Math. 338, 2212-2219 (2015) · Zbl 1318.05061 · doi:10.1016/j.disc.2015.05.030
[12] Fu, H.L., Huang, K.C.: The Hamilton-Waterloo problem for two even cycles factors. Taiwan. J. Math. 12, 933-940 (2008) · Zbl 1172.05031 · doi:10.11650/twjm/1500404987
[13] Gionfriddo, M., Milici, S.: On the existence of uniformly resolvable decompositions of \[K_v\] Kv and \[K_v-I\] Kv-I into paths and kites. Discrete Math. 313, 2830-2834 (2013) · Zbl 1281.05107 · doi:10.1016/j.disc.2013.08.023
[14] Gionfriddo, M., Milici, S.: Uniformly resolvable \[H-H\]-designs with \[H = {P_3, P_4}H=P3\],P4. Australas. J. Comb. 60, 325-332 (2014) · Zbl 1305.05189
[15] Häggkvist, R.: A lemma on cycle decompositions. Ann. Discrete Math. 27, 227-232 (1985) · Zbl 0577.05045
[16] Hoffman, D.G., Schellenberg, P.J.: The existence of \[C_k-\] Ck-factorizations of \[K_{2n}-I\] K2n-I. Discrete Math. 97, 243-250 (1991) · Zbl 0756.05089 · doi:10.1016/0012-365X(91)90440-D
[17] Horak, P., Nedela, R., Rosa, A.: The Hamilton-Waterloo problem: the case of Hamilton cycles and triangle-factors. Discrete Math. 284, 181-188 (2004) · Zbl 1066.05109 · doi:10.1016/j.disc.2003.11.031
[18] Keranen, M., Özkan, S.: The Hamilton-Waterloo problem with 4-cycles and a single factor of \[n-\] n-cycles. Graphs Comb. 29, 1827-1837 (2013) · Zbl 1282.05189 · doi:10.1007/s00373-012-1231-6
[19] Köhler, E.: Über das Oberwolfacher Problem, Beiträge zur Geometrischen Algebra, Basel, pp. 189-201 (1977) · Zbl 0384.05015
[20] Küçükçifçi, S., Milici, S., Tuza, Zs: Maximum uniformly resolvable decompositions of \[K_v\] Kv into \[3-3\]-stars and \[3-3\]-cycles. Discrete Math. 338, 1667-1673 (2015) · Zbl 1315.05113 · doi:10.1016/j.disc.2014.05.016
[21] Ling, A.C.H., Dinitz, J.H.: The Hamilton-Waterloo problem with triangle-factors and Hamilton cycles: the case \[n \equiv 3~(mod 18)\] n≡3(mod18). J Comb. Math. Comb. Comput. 70, 143-147 (2009) · Zbl 1195.05060
[22] Liu, J.: The equipartite Oberwolfach problem with uniform tables. J. Comb. Theory Ser. A 101, 20-34 (2003) · Zbl 1015.05074 · doi:10.1016/S0097-3165(02)00011-0
[23] Lucas, E.: Récréations mathématiques, vol. 2. Gauthier-Villars, Paris (1892) · JFM 15.0158.01
[24] Milici, S.: A note on uniformly resolvable decompositions of \[K_v\] Kv and \[K_v-I\] Kv-I into \[2-2\]-stars and \[4-4\]-cycles. Australas. J. Comb. 56, 195-200 (2013) · Zbl 1273.05138
[25] Milici, S., Tuza, Zs: Uniformly resolvable decompositions of \[K_v\] Kv into \[P_3\] P3 and \[K_3\] K3 graphs. Discrete Math. 331, 137-141 (2014) · Zbl 1296.05166 · doi:10.1016/j.disc.2014.05.010
[26] Odabaşı, U., Özkan, S.: The Hamilton-Waterloo problem with \[C_4\] C4 and \[C_mCm\] factors. Discrete Math. 339(1), 263-269 (2016) · Zbl 1322.05116 · doi:10.1016/j.disc.2015.08.013
[27] Piotrowski, W.L.: The solution of the bipartite analogue of the Oberwolfach problem. Discrete Math. 97, 339-356 (1991) · Zbl 0765.05080 · doi:10.1016/0012-365X(91)90449-C
[28] Piotrowski, W.L.: Untersuchungen uber das Oberwolfacher Problem. Arbeitspapier (1979) · Zbl 0995.05116
[29] Rees, R.: Two new direct product-type constructions for resolvable group-divisible designs. J. Comb. Des. 1, 15-26 (1993) · Zbl 0817.05008 · doi:10.1002/jcd.3180010104
[30] Wang, L., Chen, F., Cao, H.: The Hamilton-Waterloo problem for \[C_3-\] C3-factors and \[C_n-Cn\]-factors. J. Comb. Des. (2017). https://doi.org/10.1002/jcd.21561 · Zbl 1374.05182
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.