تقرير
Rainbow connectivity of randomly perturbed graphs
| العنوان: | Rainbow connectivity of randomly perturbed graphs |
|---|---|
| المؤلفون: | Balogh, József, Finlay, John, Palmer, Cory |
| سنة النشر: | 2021 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics |
| الوصف: | 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 \geq 5$, every pair of vertices in $G$ are joined by a rainbow path, i.e., $G$ is {\it rainbow connected}, with high probability. This confirms a conjecture of Anastos and Frieze [{\it J. Graph Theory} {\bf 92} (2019)] who proved the statement for $r \geq 7$ and resolved the case when $r \leq 4$ and $m$ is a function of $n$. Comment: Some typos and errors fixed |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2112.13277 |
| رقم الأكسشن: | edsarx.2112.13277 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |