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 Zk × R, with R a suitable ring of order m. The construction works whenever a suitable i-perfect map f:Zk → 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 ν ≡ k (mod 2k) 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.
New i-perfect cycle decompositions via vertex colorings of graphs / Buratti, Marco; Costa, Simone; Wang, Xiaomiao. - In: JOURNAL OF COMBINATORIAL DESIGNS. - ISSN 1063-8539. - 24:11(2016), pp. 495-513. [10.1002/jcd.21511]
New i-perfect cycle decompositions via vertex colorings of graphs
Buratti, Marco;
2016
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 Zk × R, with R a suitable ring of order m. The construction works whenever a suitable i-perfect map f:Zk → 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 ν ≡ k (mod 2k) 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.File | Dimensione | Formato | |
---|---|---|---|
Buratti_New i-Perfect_2016.pdf
solo gestori archivio
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
214.66 kB
Formato
Adobe PDF
|
214.66 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.