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 d ≥ 2. 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 lp norm, for any fixed 1<p≤∞). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of Kn colours, where k=k(d) 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.
| Original language | English |
|---|---|
| Pages (from-to) | 587-606 |
| Number of pages | 20 |
| Journal | Random Structures and Algorithms |
| Volume | 51 |
| Issue number | 4 |
| DOIs | |
| State | Published - 1 Dec 2017 |
Fingerprint
Keywords
- Hamilton cycles
- perfect matchings
- rainbow
- random geometric graphs
Cite this
}
Rainbow perfect matchings and Hamilton cycles in the random geometric graph. / Bal, Deepak; Bennett, Patrick; Pérez-Giménez, Xavier; Prałat, Paweł.
In: Random Structures and Algorithms, Vol. 51, No. 4, 01.12.2017, p. 587-606.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - Rainbow perfect matchings and Hamilton cycles in the random geometric graph
AU - Bal, Deepak
AU - Bennett, Patrick
AU - Pérez-Giménez, Xavier
AU - Prałat, Paweł
PY - 2017/12/1
Y1 - 2017/12/1
N2 - 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 d ≥ 2. 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 lp norm, for any fixed 1
AB - 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 d ≥ 2. 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 lp norm, for any fixed 1
KW - Hamilton cycles
KW - perfect matchings
KW - rainbow
KW - random geometric graphs
UR - http://www.scopus.com/inward/record.url?scp=85017206328&partnerID=8YFLogxK
U2 - 10.1002/rsa.20717
DO - 10.1002/rsa.20717
M3 - Article
VL - 51
SP - 587
EP - 606
JO - Random Structures and Algorithms
JF - Random Structures and Algorithms
SN - 1042-9832
IS - 4
ER -