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.
2021
mag-2021
80
2
178
196
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.
Rinaldi, Gloria
File in questo prodotto:
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

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1245681
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact