Uniform decompositions of complete multigraphs into cycles. Issue 12 (27th September 2018)

• Record Type: Journal Article
• Authors: Berry, Duncan; Bryant, Darryn; Dean, Matthew; Maenhaut, Barbara
• Is Part Of: Journal of combinatorial designs. Volume 26:Issue 12(2018:Dec.)
• Page Start: 595
• Page End: 615
• Publication Date: 2018-09-27
• Subjects: cycle decomposition -- edge decomposition -- graph decomposition -- uniform factorisation; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21630
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: The notion of uniformity, as in uniform 1 ‐factorisations, extends naturally to graph decompositions generally. The existence of uniform decompositions of complete multigraphs into cycles is investigated and some connections with families of classical designs are established. We show that if there exists a uniform decomposition of μ K n into m ‐cycles then (A) n = m and n ≤ 7, or (B) μ = 2 and m = n − 1, or (C) μ = 1, m = ( n − 1 ) ∕ 2 and n ≡ 3 ( mod 4 ) or (D) μ = 1 and 2 m ( m + 1 ) = n ( n − 1 ) . For case A, there are only a few small values of n and μ to consider, and we exhibit all uniform decompositions up to isomorphism for each such n and μ . In each of cases B and C, we construct examples of uniform decompositions for infinitely many values of n, and we investigate the isomorphism classes of our examples for each such n . We have no examples of uniform decompositions in case D, but we rule out the smallest example, namely n = 21 and m = 14, and we prove that if such decompositions exist, then so do large quasiresidual designs that are not residual.