Rainbow connectivity and rainbow criticality on graph classes.

Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph G , denoted r c (G) , is the least k for which G admits a (not necessarily proper) k -edge-coloring such that between any pair of vertices there is a path whose edge colors are all distinct. When G is disconnected, we define r c (G) = ∞. A graph G is rainbow critical if the deletion of any edge of G increases r c (G). In this paper we determine the rainbow connection number for the shadow graphs of paths, some circulant graphs, and some Cartesian products involving cycles and paths. We also determine conditions for the rainbow criticality and non-criticality of wheels, fans, and some Cartesian products involving cycles, paths, pans, and complete graphs. [ABSTRACT FROM AUTHOR]