Rainbow Connectivity and Proper Rainbow Connectivity

Abstract

A connected graph G is rainbow connected with respect to an edge coloring of G if each pair of distinct vertices of G are joined by a rainbow path--a path with no color appearing on more than one edge of the path. G is strongly rainbow connected if each pair of distinct vertices of G are joined by a rainbow geodesic, a shortest path in G between the vertices. The (strong) rainbow connection number of G, denoted (s)rc(G), is the smallest number of colors in an edge coloring of G with respect to which G is (strongly) rainbow connected.

Two more recently introduced parameters, prc and psrc, are defined as rc and src were, with the additional requirement that the edge colorings be proper. Some relations among the four parameters are mentioned and they are evaluated for some classes of graphs, including some of the theta graphs and some graphs constructed by joining arbitrarily many cycles at a cut vertex. The impact of several types of graph modifications on the values of parameters is also considered.