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

preprint2011arXivOpen access

Abstract

A path in an edge (vertex)-colored graph GG, 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)rc(G) (rvc(G)rvc(G)) of GG is the minimum integer ii for which there exists an ii-edge (vertex)-coloring of GG such that every two distinct vertices of GG are connected by a rainbow path. Denote by Gd(n)\mathcal{G}_d(n) (G′d(n)\mathcal{G'}_d(n)) the set of all graphs of order nn with rainbow (vertex) connection number dd, and define ed(n)=min⁡{e(G) ∣ G∈Gd(n)}e_d(n)=\min\{e(G)\,|\, G\in \mathcal{G}_d(n)\} (ed′(n)=min⁡{e(G) ∣ G∈G′d(n)}e_d'(n)=\min\{e(G)\,|\, G\in \mathcal{G'}_d(n)\}), where e(G)e(G) denotes the number of edges in GG. In this paper, we investigate the bounds of e2(n)e_2(n) and get the exact asymptotic value. i.e., lim⁡n→∞e2(n)nlog⁡2n=1\displaystyle \lim_{n\rightarrow \infty}\frac{e_2(n)}{n\log_2 n}=1. Meanwhile, we obtain ed′(n)=n−1e'_d(n)=n-1 for d≥2d\geq 2, and the equality holds if and only if GG is such a graph such that deleting all leaves of GG results in a tree of order dd.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.