Rainbow connectivity of randomly perturbed graphs

被引：2

作者：

Balogh, Jozsef ^{[1
]}

Finlay, John ^{[2
]}

Palmer, Cory ^{[2
]}

机构：

[1] Univ Illinois, Dept Math, Urbana, IL USA

[2] Univ Montana, Dept Math Sci, Missoula, MT 59812 USA

来源：

JOURNAL OF GRAPH THEORY | 2025年 / 109卷 / 02期

基金：

美国国家科学基金会;

关键词：

perturbed graph; rainbow connectivity; random edge-coloring; SMOOTHED ANALYSIS; RANDOM EDGES; DENSE;

D O I：

10.1002/jgt.23022

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this note we examine the following random graph model: for an arbitrary graph H, with quadratic many edges, construct a graph G by randomly adding m edges to H and randomly coloring the edges of G with r colors. We show that for m a large enough constant and r >= 5, every pair of vertices in G are joined by a rainbow path, that is, G is rainbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for r >= 7 and resolved the case when r <= 4 and m is a function of n.

引用

页码：101 / 106

页数：6

共 20 条

[1] RAINBOW HAMILTON CYCLES IN RANDOMLY COLORED RANDOMLY PERTURBED DENSE GRAPHS [J].