Hamilton Cycles in Random Lifts of Graphs
classification
🧮 math.CO
keywords
randomgraphverticescycleshamiltonianliftadjacentalmost
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{F7A4IRRI}
Prints a linked pith:F7A4IRRI badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
For a graph $G$ the random $n$-lift of $G$ is obtained by replacing each of its vertices by a set of $n$ vertices, and joining a pair of sets by a random matching whenever the corresponding vertices of $G$ are adjacent. We show that asymptotically almost surely the random lift of a graph $G$ is hamiltonian, provided $G$ has the minimum degree at least $5$ and contains two disjoint Hamiltonian cycles whose union is not a bipartite graph.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.