New i-Perfect Cycle Decompositions via Vertex Colorings of Graphs

详细信息    查看全文

• 作者：Marco Buratti ; Simone Costa and Xiaomiao Wang
• 刊名：Journal of Combinatorial Designs
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：24
• 期：11
• 页码：495-513
• 全文大小：236K
• ISSN：1520-6610

文摘

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 <mi mathvariant="double-struck">Zmi><mi>kmi>×<mi>Rmi>, with R a suitable ring of order m. The construction works whenever a suitable i-perfect map <mi>fmi>:<mi mathvariant="double-struck">Zmi><mi>kmi>⟶<mi>Rmi> exists. We show that for determining the set of all triples (<mi>imi>,<mi>kmi>,<mi>mmi>) 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 <mi>kmi>>1,000 is the product of two distinct primes, <mi>imi>>2 is even, and mits="true" form="prefix">gcd(<mi>mmi>,25)=5. This result allows us to obtain a plethora of new i-perfect k-cycle decompositions of the complete graph of order <mi>vmi>≡<mi>kmi> (mod 2k) with k odd. In particular, if k is a prime, such a decomposition exists for any possible i provided that mits="true" form="prefix">gcd(<mi>vmi><mi>kmi>,9)≠3.