|国家预印本平台
首页|Rainbow Hamilton Cycles in Random Geometric Graphs

Rainbow Hamilton Cycles in Random Geometric Graphs

Rainbow Hamilton Cycles in Random Geometric Graphs

来源:Arxiv_logoArxiv
英文摘要

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 $\cal X=\{X_1,X_2,\ldots,X_n\}$. The random geometric graph $G=G_{\cal X,r}$ has vertex set $\cal X$ and an edge $X_iX_j$ whenever $\|X_i-X_j\|\leq r$. 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.

Alan Frieze、Xavier P¨|rez-Gim¨|nez

数学

Alan Frieze,Xavier P¨|rez-Gim¨|nez.Rainbow Hamilton Cycles in Random Geometric Graphs[EB/OL].(2020-03-05)[2025-08-02].https://arxiv.org/abs/2003.02998.点此复制

评论