2021/04/14 by Bradshaw, Peter, Halasz, Kevin, Stacho, Ladislav · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2104.07020
Given a graph G and a family G = \G1,…,Gn\ 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 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 Gi ∈ 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 = Kn and each Gi ∈ G has minimum degree at least (n)/(2), then G has a Hamiltonian transversal: we show that, in this setting, G has exponentially many Hamiltonian transversals. Finally, we prove analogues of both of these theorems for transversals which form perfect matchings of G.