From one to many rainbow Hamiltonian cycles

Abstract

Given a graph $G$ and a family $\mathcal{G}=\{G_1,\dots ,G_n\}$ of subgraphs of $G$, a transversal of $\mathcal{G}$ is a pair $(T,\varphi )$ such that $T\subseteq E(G)$ and $\varphi :T\to [n]$ is a bijection satisfying $e\in G_{\varphi (e)}$ for each $e\in 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 $G_i\in \mathcal{G}$, for every $\mathcal{G}$ which contains a Hamiltonian transversal, the number of Hamiltonian transversals contained in $\mathcal{G}$ is bounded below by a function of $G$'s maximum degree. This generalizes a theorem of Thomassen stating that, for $m\ge 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\in \mathcal{G}$ has minimum degree at least $\frac{n}{2}$, then $\mathcal{G}$ has a Hamiltonian transversal: we show that, in this setting, $\mathcal{G}$ has exponentially many Hamiltonian transversals. Finally, we prove analogues of both of these theorems for transversals which form perfect matchings of $G$.

13 pages, 1 figure