Rainbow connection numbers of complementary graphs
Abstract
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 Ḡ. We first derive that for a connected graph G, if Ḡ does not belong to the following two cases: (i) diam(Ḡ) = 2,3, (ii) G contains exactly two connected components and one of them is trivial, then rc(G) ≤ 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 Ḡ is triangle-free, then rc(G) ≤ 6.
