Name
Abstract | ||
|---|---|---|
AbstractGiven 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 ï źp norm, for any fixed 1 |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1002/rsa.20717 | Periodicals |
Keywords | Field | DocType |
perfect matchings,Hamilton cycles,random geometric graphs,rainbow | Pseudoforest,Discrete mathematics,Geometric graph theory,Combinatorics,Cycle graph,Degree (graph theory),Factor-critical graph,Multiple edges,Mathematics,Complement graph,Path graph | Journal |
Volume | Issue | ISSN |
51 | 4 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deepak Bal | 1 | 35 | 7.32 |
| P BENNETT | 2 | 15 | 5.42 |
| Xavier Pérez-Giménez | 3 | 31 | 4.75 |
| Pawel Pralat | 4 | 234 | 48.16 |