Rainbow k-connectivity of some Cartesian product graphs
Yan Zhao, Sujuan Liu · 2017
A path is rainbow if no two edges of it are colored the same. For a κ-connected graph G and an integer k with 1 ≤ k ≤ κ, the rainbow k-connectivity rck(G) is the the minimum integer t for which there exists a t-edge-coloring of G such that for every two distinct vertices u and v of G, there exist at least k internally disjoint rainbow (u, v)-paths. This concept of rainbow k-connectivity, introduced by Chartrand et al., is a natural generalization of the rainbow connection number of a graph and has multiple applications in networks security. The Cartesian product of two graphs G and H, denoted by G□H, is an important method to construct large graphs from small ones and plays a key role in design and analysis of networks. In this paper, we obtain some results for rainbow k-connectivity of Cartesian product graphs.