Rainbow Hamilton Cycles in Random Geometric Graphs

DOI10.1002/RSA.21201MaRDI QIDQ6336225zbMATH OpenOpenAlexFDO

Authors Alan Frieze, Xavier Pérez-Giménez

Publication date 5 March 2020

Full work available at URL https://doi.org/10.1002/rsa.21201

Mathematics Subject Classification ID

Probability theory and stochastic processes (60-XX) Eulerian and Hamiltonian graphs (05C45)

Abstract: Let $X_1,X_2,ldots,X_n$ be chosen independently and uniformly at random from the unit $d$-dimensional cube $[0,1{]}^d$. Let $r$ be given and let $calX=X_1,X_2,ldots,X_n$. The random geometric graph $G=G_{calX,r}$ has vertex set $calX$ and an edge $X_i{X}_j$ whenever $|X_i-X_j|leqr$. We show that if each edge of $G$ is colored independently from one of $n+o(n)$ colors and $r$ has the smallest value such that $G$ has minimum degree at least two, then $G$ contains a rainbow Hamilton cycle a.a.s.

Recommendations

• Rainbow perfect matchings and Hamilton cycles in the random geometric graph
• Rainbow Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random regular graphs
• On rainbow Hamilton cycles in random hypergraphs
• Rainbow Hamilton cycles in random graphs and hypergraphs

This page was built for publication: Rainbow Hamilton Cycles in Random Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6336225)