×

zbMATH — the first resource for mathematics

\(i\)-perfect \(m\)-cycle systems, \(m\leq 19\). (English) Zbl 0883.05110
An \(m\)-cycle decomposition of a graph \(G\) is a pair \((V,C)\), where \(V\) is the vertex set of \(G\), and \(C\) is a collection of edge-disjoint \(m\)-cycles in \(G\) which cover its edges. In the case \(G\) is the complete graph, \(K_v\), \((V(G),C)\) is called an \(m\)-cycle system of order \(v\). If \(c\) is a cycle of length \(m\), then let \(c(i)\) denote the graph formed from \(c\) by joining all vertices in \(c\) at distance \(i\). If \((V,C)\) is an \(m\)-cycle decomposition of \(G\) such that \((V, \{c(i) \mid c\in C\})\) is also a cycle decomposition of \(G\), then we call \((V,C)\) an \(i\)-perfect \(m\)-cycle decomposition of \(G\). For all \(m\leq 19\) and each meaningful value of \(i\) (\(2\leq i \leq \lfloor m/2\rfloor\)), the spectrum problem for \(i\)-perfect \(m\)-cycle systems is examined. The authors describe several constructions for \(i\)-perfect \(m\)-cycle systems and they construct several new \(i\)-perfect \(m\)-cycle systems for \(m\leq 19\). The paper contains a table summarizing all of the new and known results for \(i\)-perfect \(m\)-cycle systems for \(5\leq m\leq 19\).

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B30 Other designs, configurations
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Adams, P.,Combinatorial designs and related computational constructions. PhD thesis, Univ. Queensland, 1995. · Zbl 0879.05047
[2] Adams, P. andBillington, E. J.,Completing some spectra for 2-perfect cycle systems. Australas. J. Combin.7 (1993), 175–187. · Zbl 0777.05014
[3] Adams, P. andBillington, E. J.,The spectrum for 2-perfect 8-cycle systems. Ars Combin. (to appear).
[4] Adams, P., Billington, E. J. andBryant, D. E.,Partitionable perfect cycle systems with cycle lengths 6 and 8. Discrete Math. (to appear). · Zbl 0849.05014
[5] Adams, P., Billington, E. J. andLindner, C. C.,The spectrum for 3-perfect 9-cycle systems. Australas. J. Combin.5 (1992), 103–108. · Zbl 0774.05075
[6] Adams, P., Billington, E. J. andLindner, C. C.,k-perfect 3k-cycle systems. J. Combin. Math. Combin. Comput.15 (1994) 141–154. · Zbl 0806.05045
[7] Adams, P. andBryant, D. E.,Cyclically generated m-trail systems of order 2m + 1, m 10. J. Combin. Math. Combin. Comput.17 (1995) 3–19. · Zbl 0821.05033
[8] Adams, P. andBryant, D. E.,Computationally constructed i-perfect m-cycle system. Technical Report, Centre for Combinatorics, Univ. Queensland, 1996.
[9] Billington, E. J. andLindner, C. C.,The spectrum for lambda-fold 2-perfect 6-cycle systems. European J. Combinatorics5 (1992), 5–14. · Zbl 0754.05046 · doi:10.1016/0195-6698(92)90063-6
[10] Brouwer, A. E.,Optimal packings of K 4’s into a Kn. J. Combin. Theory Ser. A26 (1979), 278–297. · Zbl 0412.05030 · doi:10.1016/0097-3165(79)90105-5
[11] Brouwer, A. E., Schrijver, A. andHanani, H.,Group divisible designs with block-size four. Discrete Math.20 (1977), 1–10. · Zbl 0371.62105 · doi:10.1016/0012-365X(77)90037-1
[12] Bryant, D. E. andLindner, C. C.,2-perfect m-cycle systems can be equationally defined for m = 3, 5 and 7 only. Algebra Universalis35 (I) (1996), 1–7. · Zbl 0855.05039 · doi:10.1007/BF01190966
[13] Colbourn, C. J., Hoffman, D. G. andRees, R.,A new class of group divisible designs with block size three. J. Combin. Theory, Ser. A.59 (1992), 73–89. · Zbl 0759.05012 · doi:10.1016/0097-3165(92)90099-G
[14] Colbourn, C. J. andStinson, D. R.,Edge-coloured designs with block size four. Aequationes Mathematicae36 (1988), 230–245. · Zbl 0658.05016 · doi:10.1007/BF01836093
[15] Lindner, C. C.,Graph decompositions and quasigroup identities. In Proceedings of the Second International Catania Combinatorial Conference, ”Graphs, designs and combinatorial geometries”, Universit√† di Catania, Catania, Sicily, September 4–9, 1989. Le Matematiche45 (1990), 83–118.
[16] Lindner, C. C., Phelps, K. T. andRodger, C. A. The spectrum for 2-perfect 6-cycle systems. J. Combin. Theory Ser. A57 (1991), 76–85. · Zbl 0758.05015 · doi:10.1016/0097-3165(91)90007-4
[17] Lindner, C. C. andRodger, C. A.,Decomposition into cycles II: Cycle systems in Contemporary design theory: a collection of surveys (J. H. Dinitz and D. R. Stinson, eds.). John Wiley and Sons, New York, 1992, 325–369.
[18] Lindner, C. C. andRodger, C. A.,2-perfect m-cycle systems. Discrete Math.104 (1992), 83–90. · Zbl 0766.05045 · doi:10.1016/0012-365X(92)90626-Q
[19] Lindner, C. C. andStinton, D. R.,Steiner pentagon systems. Discrete Math.52 (1984), 67–74. · Zbl 0549.05010 · doi:10.1016/0012-365X(84)90104-3
[20] Manduchi, E.,Steiner heptagon systems. Ars Combin.31 (1991), 105–115. · Zbl 0748.05019
[21] Rodger, C. A.,Graph decompositions. Le Matematiche45 (1990), 119–140. · Zbl 0735.05066
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.