How many randomly colored edges make a randomly colored dense graph rainbow Hamiltonian or rainbow connected?

被引：7

作者：

Anastos, Michael ^{[1
]}

Frieze, Alan ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

JOURNAL OF GRAPH THEORY | 2019年 / 92卷 / 04期

基金：

美国国家科学基金会;

关键词：

add random edges; dense graphs; random edge coloring;

D O I：

10.1002/jgt.22461

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：405 / 414

页数：10

共 14 条

[1] Adding random edges to dense graphs [J].