From One to Many Rainbow Hamiltonian Cycles

• Published in: Graphs and combinatorics 2022-12, Vol.38 (6), Article 188
• Main Authors: Bradshaw, Peter, Halasz, Kevin, Stacho, Ladislav
• Format: Article
• Language: English
• Subjects: Combinatorics; Engineering Design; Graph theory; Mathematics; Mathematics and Statistics; Original Paper; Theorems
• ISSN: 0911-0119; 1435-5914
• DOI: 10.1007/s00373-022-02574-z

Given a graph G and a family G = { G 1 , … , G n } of subgraphs of G , a transversal of G is a pair ( T , ϕ ) such that T ⊆ E ( G ) and ϕ : T → [ n ] is a bijection satisfying e ∈ G ϕ ( e ) for each e ∈ T . We call a transversal ( T , ϕ ) Hamiltonian if T corresponds to the edge set of a Hamiltonian cycle in G . We show that, under certain conditions on the maximum degree of G and the minimum degrees of the G i ∈ G , for every G which contains a Hamiltonian transversal, the number of Hamiltonian transversals contained in G is bounded below by a function of G ’s maximum degree. This generalizes a theorem of Thomassen stating that, for m ≥ 300 , no m -regular graph is uniquely Hamiltonian. We also extend Joos and Kim’s recent result that, if G = K n and each G i ∈ G has minimum degree at least n /2, then G has a Hamiltonian transversal: we show that, in this setting, G has factorially many Hamiltonian transversals. Finally, we prove analogues of both of these theorems for transversals which form perfect matchings in G .