The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths

Bety Hayat Susanti (Sekolah Tinggi Sandi Negara)
A.N.M. Salman (Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung)
Rinovia Simanjuntak (Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 8, No 1 (2020): Electronic Journal of Graph Theory and Applications

An edge-colored graph G is rainbow k-connected, if there are k-internally disjoint rainbow paths connecting every pair of vertices of G. The rainbow k-connection number of G, denoted by rck(G), is the minimum number of colors needed for which there exists a rainbow k-connected coloring for G. In this paper, we are able to find sharp lower and upper bounds for the rainbow 2-connection number of Cartesian products of arbitrary 2-connected graphs and paths. We also determine the rainbow 2-connection number of the Cartesian products of some graphs, i.e. complete graphs, fans, wheels, and cycles, with paths.