The rainbow connectivity of cartesian product graphs
Xing Chen, Xueliang Li, Jianfeng Wang, Nannan Fan · Journal of Discrete Mathematical Sciences and Cryptography · 2019
An edge-coloured graph G is said to be rainbow-connected if any two vertices are connected by a path whose edges have different colours. The rainbow connection number of a graph is the minimum number of colours needed to make the graph rainbow-connected. This parameter was introduced by G. Chartrand, G.L. Johns, K.A. McKeon and P. Zhang in 2008. Similar to rainbow connection coloring, an edge-coloring is a rainbow k-connection coloring if there are at least k internally disjoint rainbow u – v paths connecting any two distinct vertices u and v. And the rainbow k-connectivity rck(G) of G to be the minimum integer l such that there exists a l-edge-coloring which is a rainbow k-connection coloring. In [4], the authors determined the rck(G) of the complete graph Kn and r-regular complete bipartite graphs Kr, r. In this paper, we study the rainbow k-connectivity of the Cartesian product graphs K2□Kn for some k. We determine rck(K2□Kn) for k = 2, 3, 4 and prove that there exists Cartesian product graphs K2□Kn such that rck(K2□Kn) = 3 for each integer k ≥ 2.