From one to many rainbow Hamiltonian cycles
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,\phi)\) such that \(T \subseteq E(G)\) and \(\phi : T \rightarrow [n]\) is a bijection satisfying \(e \in G_{\phi(e)}\) for each \(e \in T\). Informally, a transversal is a set of edges that uses exactly one edge from each subgraph \(G_i \in \mathcal{G}\). A transversal \((T,\phi)\) is called a Hamiltonian transversal of \(\mathcal{G}\) if \(T\) corresponds to the edge set of a Hamiltonian cycle of \(G\). \textit{F. Joos} and \textit{J. Kim} [Bull. Lond. Math. Soc. 52, No. 3, 498--504 (2020; Zbl 1444.05078)] proved that if \(G=K_n\) and \(\mathcal{G} = \{ G_1, \dots , G_n \}\) satisfies \(\delta(G_i) \geq n/2\) for each \(i \in [n]\), then there exists a Hamiltonian transversal of \(\mathcal{G}\). This generalizes Dirac's classic sufficient minimum degree condition [\textit{G. A. Dirac}, Proc. Lond. Math. Soc. (3) 2, 69--81 (1952; Zbl 0047.17001)] for a Hamiltonian cycle. Similarly, the first author showed in [``An asymptotic for the Hall-Paige conjecture, Preprint, \url{arXiv:2003.01798}] that a similar condition of \textit{J. Moon} and \textit{L. Moser} [Isr. J. Math. 1, 163--165 (1963; Zbl 0119.38806)] for Hamiltonicity in bipartite graphs can be generalized into the setting of transversals. This paper continues the project of generalizing results related to Hamiltonicity into the language of graph transversals. For example, the authors show that under certain conditions on the maximum degree of \(G\) and the minimum degrees of \(G_i \in \mathcal{G}\), for every \(\mathcal{G}\) which contains a Hamiltonian transversal, the number of Hamiltonian transversals of \(\mathcal{G}\) is bounded below by a function of the maximum degree of \(G\). This generalizes a theorem of [\textit{C. Thomassen}, J. Comb. Theory, Ser. B 72, No. 1, 104--109 (1998; Zbl 0895.05038)] stating that, for \(m \geq 300\), no \(m\)-regular graph is uniquely Hamiltonian.
- \(4\)-regular \(4\)-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
- A lower bound on the number of hamiltonian cycles
- A rainbow version of Mantel's theorem
- Additive triples of bijections, or the toroidal semiqueens problem
- Almost all Steiner triple systems have perfect matchings
- An approximate version of a conjecture of Aharoni and Berger
- An asymptotic for the Hall-Paige conjecture
- Chords of longest cycles in cubic graphs
- Density of Gallai multigraphs
- Hamiltonian Cycles and Uniquely Edge Colourable Graphs
- Hamiltonian cycles in Dirac graphs
- scientific article; zbMATH DE number 46958 (Why is no real title available?)
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- Independent dominating sets and a second hamiltonian cycle in regular graphs
- Independent dominating sets and hamiltonian cycles
- On a rainbow version of Dirac's theorem
- On Hamiltonian bipartite graphs
- On perfect matchings in uniform hypergraphs with large minimum vertex degree
- On the minimum number of Hamiltonian cycles in regular graphs
- On the numbers of 1-factors and 1-factorizations of hypergraphs
- Paths, Trees, and Flowers
- Perfect matchings in 3-partite 3-uniform hypergraphs
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- Probability and Computing
- Rainbow matchings and transversals
- Rainbow perfect matchings in complete bipartite graphs: existence and counting
- Regular graphs with few longest cycles
- Representation of large matchings in bipartite graphs
- Some Matching Problems for Bipartite Graphs
- Some Theorems on Abstract Graphs
- Transversals and bipancyclicity in bipartite graph families
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs
- Concentration of rainbow \(k\)-connectivity of a multiplex random graph
- Transversal factors and spanning trees
- A general approach to transversal versions of Dirac‐type theorems
- From one to many rainbow Hamiltonian cycles
- Rainbow Pancyclicity in a Collection of Graphs Under the Dirac-type Condition
- Vertex-bipancyclicity in a bipartite graph collection
- Transversal Hamilton cycle in hypergraph systems
- Stability of transversal Hamilton cycles and paths
- Rainbow directed version of Dirac's theorem
- Universality for transversal Hamilton cycles
- Dirac-type condition for rainbow chorded pancyclicity
- Transversal Hamilton paths and cycles
- Transversal Hamilton cycle in the hypergraph system
This page was built for publication: From one to many rainbow Hamiltonian cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2102759)
