Asymptotic value of the minimal size of a graph with rainbow connection number 2

Abstract

A path in an edge (vertex)-colored graph $G$, where adjacent edges (vertices) may have the same color, is called a rainbow path if no pair of edges (internal vertices) of the path are colored the same. The rainbow (vertex) connection number $rc(G)$ ($rvc(G)$) of $G$ is the minimum integer $i$ for which there exists an $i$-edge (vertex)-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. Denote by ${\mathcal{G}}_d(n)$ (${{\mathcal{G}}^{\prime }}_d(n)$) the set of all graphs of order $n$ with rainbow (vertex) connection number $d$, and define $e_d(n)=\min \{e(G)|G\in {\mathcal{G}}_d(n)\}$ ($e_d^{\prime }(n)=\min \{e(G)|G\in {{\mathcal{G}}^{\prime }}_d(n)\}$), where $e(G)$ denotes the number of edges in $G$. In this paper, we investigate the bounds of $e_2(n)$ and get the exact asymptotic value. i.e., $\underset{n\to \infty }{\lim }\frac{e_2(n)}{n{\log }_{2}n}=1$. Meanwhile, we obtain $e_d^{\prime }(n)=n-1$ for $d\ge 2$, and the equality holds if and only if $G$ is such a graph such that deleting all leaves of $G$ results in a tree of order $d$.

8 pages