Rainbow connection number and stable number

Details Rainbow connection number and stable number Rainbow connection number and stable number

2012-04-19

arxiv.org/abs/1204.4298v2

Mathematics

Combinatorics

12 pages

Scientific paper

Let $G$ be an edge-colored connected graph. A rainbow path of $G$ is such a path that no two edges of it are colored the same. For any two vertices $u$ and $v$ of $G$, if there is a rainbow path connecting $u$ and $v$, we say that $G$ is rainbow connected. The rainbow connection number $rc(G)$ of $G$ is the smallest number of colors that are needed to make $G$ rainbow connected. There are many results on the relations between the rainbow connection number and other parameters, such as the minimum degree $\delta(G)$ and average degree, the minimum degree sum, the radius and diameter, the circumference and the chromatics number, etc. In this paper, we obtain a relationship between the rainbow connection number and the stable number $\alpha(G)$ (the cardinality of a maximum stable set of $G$), that is, if $G$ is a connected graph with $\alpha(G)=\alpha$ and $\delta(G)\geq 2$, then $rc(G)\leq 2\alpha-1$. Examples are given to show that the upper bound is sharp.

Affiliated with

Also associated with

No associations

Rating

Rainbow connection number and stable number 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 Rainbow connection number and stable number, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow connection number and stable number will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-34742