Rainbow perfect matchings and Hamilton cycles in the random geometric graph

DOI10.1002/RSA.20717zbMATH Open1386.05173DBLPjournals/rsa/BalBPP17arXiv1602.05169OpenAlexW2963663072WikidataQ57991415 ScholiaQ57991415MaRDI QIDQ4597602FDOQ4597602

Authors: Deepak Bal, Patrick Bennett, Xavier Pérez-Giménez, Paweł Prałat 

Publication date: 13 December 2017

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: Given a graph on $n$ vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length $n$ visiting each vertex once and with pairwise different colours on the edges. Similarly (for even $n$) a rainbow perfect matching is a collection of $n/2$ independent edges with pairwise different colours. In this note we show that if we randomly colour the edges of a random geometric graph with sufficiently many colours, then a.a.s. the graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and only if the minimum degree is at least $1$ (respectively, at least $2$). More precisely, consider $n$ points (i.e. vertices) chosen independently and uniformly at random from the unit $d$-dimensional cube for any fixed $dge2$. Form a sequence of graphs on these $n$ vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of lengths (measured with respect to the $el{l}_p$ norm, for any fixed $1<pleinfty$). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of $lceilKnceil$ colours, where $K=K(d)$ is a sufficiently large fixed constant. Then, a.a.s. the first graph in the sequence with minimum degree at least $1$ must contain a rainbow perfect matching (for even $n$), and the first graph with minimum degree at least $2$ must contain a rainbow Hamilton cycle.

Full work available at URL: https://arxiv.org/abs/1602.05169

Recommendations

• Rainbow matchings and Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Rainbow Hamilton cycles in random graphs
• Rainbow Hamilton cycles in random regular graphs
• Rainbow Hamilton cycles in randomly colored randomly perturbed dense graphs

zbMATH Keywords

rainbowperfect matchingsHamilton cyclesrandom geometric graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• Rainbow Hamilton Cycles in Random Geometric Graphs
• Powers of Hamilton cycles in dense graphs perturbed by a random geometric graph
• Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\)
• Rainbow Hamilton cycles in random regular graphs
• Bridged Hamiltonian cycles in sub-critical random geometric graphs

This page was built for publication: Rainbow perfect matchings and Hamilton cycles in the random geometric graph

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