Mathematics – Combinatorics
Scientific paper
2010-11-20
Mathematics
Combinatorics
9 pages
Scientific paper
A path in an edge-colored graph, where adjacent edges may be colored the same, is a rainbow path if no two edges of it are colored the same. A nontrivial connected graph $G$ is rainbow connected if there is a rainbow path connecting any two vertices, and the rainbow connection number of $G$, denoted by $rc(G)$, is the minimum number of colors that are needed in order to make $G$ rainbow connected. In this paper, we provide a new approach to investigate the rainbow connection number of a graph $G$ according to some constraints to its complement graph $\bar{G}$. We first derive that for a connected graph $G$, if $\bar{G}$ does not belong to the following two cases: $(i)$~$diam(\bar{G})=2,3$, $(ii)~\bar{G}$ contains exactly two connected components and one of them is trivial, then $rc(G)\leq 4$, where $diam(G)$ is the diameter of $G$. Examples are given to show that this bound is best possible. Next we derive that for a connected graph $G$, if $\bar{G}$ is triangle-free, then $rc(G)\leq 6$.
Li Xueliang
Sun Yuefang
No associations
LandOfFree
Rainbow connection numbers of complementary 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 Rainbow connection numbers of complementary graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow connection numbers of complementary graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-21782