TY - JOUR

T1 - Rainbow connectivity of randomly perturbed graphs

AU - Balogh, József

AU - Finlay, John

AU - Palmer, Cory

N1 - Publisher Copyright:
© 2023 Wiley Periodicals LLC.

PY - 2023

Y1 - 2023

N2 - In this note we examine the following random graph model: for an arbitrary graph (Formula presented.), with quadratic many edges, construct a graph (Formula presented.) by randomly adding (Formula presented.) edges to (Formula presented.) and randomly coloring the edges of (Formula presented.) with (Formula presented.) colors. We show that for (Formula presented.) a large enough constant and (Formula presented.), every pair of vertices in (Formula presented.) are joined by a rainbow path, that is, (Formula presented.) is rainbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for (Formula presented.) and resolved the case when (Formula presented.) and (Formula presented.) is a function of (Formula presented.).

AB - In this note we examine the following random graph model: for an arbitrary graph (Formula presented.), with quadratic many edges, construct a graph (Formula presented.) by randomly adding (Formula presented.) edges to (Formula presented.) and randomly coloring the edges of (Formula presented.) with (Formula presented.) colors. We show that for (Formula presented.) a large enough constant and (Formula presented.), every pair of vertices in (Formula presented.) are joined by a rainbow path, that is, (Formula presented.) is rainbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for (Formula presented.) and resolved the case when (Formula presented.) and (Formula presented.) is a function of (Formula presented.).

KW - perturbed graph

KW - rainbow connectivity

KW - random edge-coloring

UR - http://www.scopus.com/inward/record.url?scp=85167329112&partnerID=8YFLogxK

U2 - 10.1002/jgt.23022

DO - 10.1002/jgt.23022

M3 - Article

AN - SCOPUS:85167329112

SN - 0364-9024

JO - Journal of Graph Theory

JF - Journal of Graph Theory

ER -