Premium
Uniform decompositions of complete multigraphs into cycles
Author(s) -
Berry Duncan,
Bryant Darryn,
Dean Matthew,
Maenhaut Barbara
Publication year - 2018
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21630
Subject(s) - mathematics , isomorphism (crystallography) , combinatorics , graph , residual , graph isomorphism , decomposition , discrete mathematics , algorithm , line graph , ecology , chemistry , crystal structure , biology , crystallography
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.