Premium
How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?
Author(s) -
Anastos Michael,
Frieze Alan
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22461
Subject(s) - colored , rainbow , combinatorics , mathematics , hamiltonian path , wheel graph , disjoint sets , complement graph , graph , discrete mathematics , path graph , complete graph , edge coloring , graph power , line graph , physics , optics , materials science , composite material
In this paper, we study the randomly edge colored graph that is obtained by adding randomly colored random edges to an arbitrary randomly edge colored dense graph. In particular, we ask how many colors and how many random edges are needed so that the resultant graph contains a fixed number of edge‐disjoint rainbow‐Hamilton cycles w.h.p. We also ask when, in the resultant graph, every pair of vertices is connected by a rainbow path w.h.p.