New i‐Perfect Cycle Decompositions via Vertex Colorings of Graphs. Issue 11 (22nd January 2016)

• Record Type: Journal Article
• Authors: Buratti, Marco; Costa, Simone; Wang, Xiaomiao
• Is Part Of: Journal of combinatorial designs. Volume 24:Issue 11(2016:Nov.)
• Page Start: 495
• Page End: 513
• Publication Date: 2016-01-22
• Subjects: i‐perfect cycle decomposition -- group action -- vertex coloring; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21511
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: Generalizing a result by Buratti et al.[M. Buratti, F. Rania, and F. Zuanni, Some constructions for cyclic perfect cycle systems, Discrete Math 299 (2005), 33–48], we present a construction for i ‐perfect k ‐cycle decompositions of the complete m ‐partite graph with parts of size k . These decompositions are sharply vertex‐transitive under the additive group of Z k × R, with R a suitable ring of order m . The construction works whenever a suitable i‐perfect map f : Z k ⟶ R exists. We show that for determining the set of all triples ( i, k, m ) for which such a map exists, it is crucial to calculate the chromatic numbers of some auxiliary graphs. We completely determine this set except for one special case where k > 1, 000 is the product of two distinct primes, i > 2 is even, and gcd ( m, 25 ) = 5 . This result allows us to obtain a plethora of new i ‐perfect k ‐cycle decompositions of the complete graph of order v ≡ k (mod 2 k ) with k odd. In particular, if k is a prime, such a decomposition exists for any possible i provided that gcd ( v k, 9 ) ≠ 3 .