A sharp upper bound for the rainbow 2-connection number of 2-connected graphs

Details A sharp upper bound for the rainbow 2-connection number of 2-connected graphs A sharp upper bound for the rainbow 2-connection number of 2-connected graphs

2012-04-02

arxiv.org/abs/1204.0392v2

Mathematics

Combinatorics

8 pages

Scientific paper

A path in an edge-colored graph is called {\em rainbow} if no two edges of it are colored the same. For an $\ell$-connected graph $G$ and an integer $k$ with $1\leq k\leq \ell$, the {\em rainbow $k$-connection number} $rc_k(G)$ of $G$ is defined to be the minimum number of colors required to color the edges of $G$ such that every two distinct vertices of $G$ are connected by at least $k$ internally disjoint rainbow paths. Fujita et. al. proposed a problem that what is the minimum constant $\alpha>0$ such that for all 2-connected graphs $G$ on $n$ vertices, we have $rc_2(G)\leq \alpha n$. In this paper, we prove that $\alpha=1$ and $rc_2(G)=n$ if and only if $G$ is a cycle of order $n$, settling down this problem.

Affiliated with

Also associated with

No associations

Rating

A sharp upper bound for the rainbow 2-connection number of 2-connected graphs 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 A sharp upper bound for the rainbow 2-connection number of 2-connected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A sharp upper bound for the rainbow 2-connection number of 2-connected graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-509586