## Abstract

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.).

Original language | English (US) |
---|---|

Journal | Journal of Graph Theory |

DOIs | |

State | Accepted/In press - 2023 |

## Keywords

- perturbed graph
- rainbow connectivity
- random edge-coloring

## ASJC Scopus subject areas

- Geometry and Topology
- Discrete Mathematics and Combinatorics