Note on minimally $k$-rainbow connected graphs

Details Note on minimally $k$-rainbow connected graphs Note on minimally $k$-rainbow connected graphs

2012-03-14

arxiv.org/abs/1203.3030v1

Mathematics

Combinatorics

8 pages

Scientific paper

An edge-colored graph $G$, where adjacent edges may have the same color, is {\it rainbow connected} if every two vertices of $G$ are connected by a path whose edge has distinct colors. A graph $G$ is {\it $k$-rainbow connected} if one can use $k$ colors to make $G$ rainbow connected. For integers $n$ and $d$ let $t(n,d)$ denote the minimum size (number of edges) in $k$-rainbow connected graphs of order $n$. Schiermeyer got some exact values and upper bounds for $t(n,d)$. However, he did not get a lower bound of $t(n,d)$ for $3\leq d<\lceil\frac{n}{2}\rceil $. In this paper, we improve his lower bound of $t(n,2)$, and get a lower bound of $t(n,d)$ for $3\leq d<\lceil\frac{n}{2}\rceil$.

Affiliated with

Also associated with

No associations

Rating

Note on minimally $k$-rainbow 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 Note on minimally $k$-rainbow connected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Note on minimally $k$-rainbow connected graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-715473