Mathematics – Combinatorics
Scientific paper
2011-05-22
Mathematics
Combinatorics
8 pages
Scientific paper
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'}_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'(n)=\min\{e(G)\,|\, G\in \mathcal{G'}_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., $\displaystyle \lim_{n\rightarrow \infty}\frac{e_2(n)}{n\log_2 n}=1$. Meanwhile, we obtain $e'_d(n)=n-1$ for $d\geq 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$.
Li Hengzhe
Li Xueliang
Sun Yuefang
No associations
LandOfFree
Asymptotic value of the minimal size of a graph with rainbow connection number 2 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Asymptotic value of the minimal size of a graph with rainbow connection number 2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic value of the minimal size of a graph with rainbow connection number 2 will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-329971