A 1-factorization F of a complete graph K2n is said to be G-regular, or regular under G, if G is an automorphism group of F acting sharply transitively on the vertex-set. The problem of determining which groups can realize such a situation dates back to a result by Hartman and Rosa (1985) on cyclic groups, and it is still open even though several other classes of groups were tested in the recent past. An attempt to obtain a fairly precise description of groups and 1-factorizations satisfying this symmetry constraint can be done by imposing further conditions. In this paper we prove that, regardless of the isomorphism type of G, the existence of a G-regular 1-factorization of K2n together with a complete set of isomorphic rainbow spanning trees which are in the orbit of a single one is assured if and only if n ≥ 3 is an odd number. Also, when n is even, we examine dihedral groups: for each dihedral group G of order 2n ≥ 6, it is possible to exhibit a G-regular 1-factorization of K2n together with two non isomorphic rainbow spanning trees whose partial orbits give rise to a complete set. This extends some recent results obtained by Caughman et al. (2017) and by Mazzuoccolo et al. (2019) for the class of cyclic groups.
Regular 1-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees / Rinaldi, Gloria. - In: THE AUSTRALASIAN JOURNAL OF COMBINATORICS. - ISSN 2202-3518. - 80:2(2021), pp. 178-196.
Regular 1-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees
Gloria Rinaldi
2021
Abstract
A 1-factorization F of a complete graph K2n is said to be G-regular, or regular under G, if G is an automorphism group of F acting sharply transitively on the vertex-set. The problem of determining which groups can realize such a situation dates back to a result by Hartman and Rosa (1985) on cyclic groups, and it is still open even though several other classes of groups were tested in the recent past. An attempt to obtain a fairly precise description of groups and 1-factorizations satisfying this symmetry constraint can be done by imposing further conditions. In this paper we prove that, regardless of the isomorphism type of G, the existence of a G-regular 1-factorization of K2n together with a complete set of isomorphic rainbow spanning trees which are in the orbit of a single one is assured if and only if n ≥ 3 is an odd number. Also, when n is even, we examine dihedral groups: for each dihedral group G of order 2n ≥ 6, it is possible to exhibit a G-regular 1-factorization of K2n together with two non isomorphic rainbow spanning trees whose partial orbits give rise to a complete set. This extends some recent results obtained by Caughman et al. (2017) and by Mazzuoccolo et al. (2019) for the class of cyclic groups.File | Dimensione | Formato | |
---|---|---|---|
ajc_v80_p178-196.pdf
Open access
Tipologia:
Versione pubblicata dall'editore
Dimensione
178.89 kB
Formato
Adobe PDF
|
178.89 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris