Nordhaus---Gaddum-Type Theorem for Rainbow Connection Number of Graphs

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G , denoted by rc ( G ), is the mi...