{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:23Z","timestamp":1759638023816,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>An edge colored graph $G$ is rainbow edge connected if any two vertices are connected\u00a0by a path whose edges have distinct colors. The rainbow connectivity of a connected\u00a0graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in\u00a0order to make $G$ rainbow connected. In this work we study the rainbow connectivity of binomial random graphs\u00a0at the connectivity threshold $p=\\frac{\\log n+\\omega}{n}$ where $\\omega=\\omega(n)\\to\\infty$ and ${\\omega}=o(\\log{n})$\u00a0and of random $r$-regular graphs where $r \\geq 3$ is a fixed integer.\u00a0Specifically, we prove that the rainbow connectivity $rc(G)$ of $G=G(n,p)$ satisfies $rc(G) \\sim \\max\\{Z_1,\\text{diam}(G)\\}$\u00a0with high probability (whp). Here $Z_1$ is the number of vertices in $G$ whose degree equals 1 and the diameter of $G$\u00a0is asymptotically equal to $\\frac{\\log n}{\\log\\log n}$ whp.\u00a0Finally, we prove that the rainbow connectivity $rc(G)$ of the random $r$-regular graph $G=G(n,r)$ whp\u00a0satisfies $rc(G) =O(\\log^{2\\theta_r}{n})$ where $\\theta_r=\\frac{\\log (r-1)}{\\log (r-2)}$\u00a0when $r\\geq 4$ and $rc(G) =O(\\log^4n)$ whp when $r=3$.<\/jats:p>","DOI":"10.37236\/2784","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T03:12:25Z","timestamp":1578712345000},"source":"Crossref","is-referenced-by-count":9,"title":["Rainbow Connection of Sparse Random Graphs"],"prefix":"10.37236","volume":"19","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charalampos E.","family":"Tsourakakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2012,10,18]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v19i4p5\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v19i4p5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T22:28:48Z","timestamp":1579300128000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v19i4p5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,18]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2012,10,18]]}},"URL":"https:\/\/doi.org\/10.37236\/2784","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2012,10,18]]},"article-number":"P5"}}