The rainbow connectivity of cartesian product graphs. (18th August 2019)

• Record Type: Journal Article
• Authors: Chen, Xing; Li, Xueliang; Wang, Jianfeng; Fan, Nannan
• Is Part Of: Journal of discrete mathematical sciences & cryptography. Volume 22:Number 6(2019)
• Page Start: 901
• Page End: 914
• Publication Date: 2019-08-18
• Subjects: 05C40 -- Edge coloring -- Rainbow-connected graph -- Rainbow k-connectivity; Computer science -- Mathematics -- Periodicals; Cryptography -- Periodicals; Computer science -- Mathematics; Cryptography; Periodicals; 004.0151
• DOI: 10.1080/09720529.2019.1614337
• Languages: English
• ISSNs: 0972-0529

Abstract

Abstract: 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 K 2 □ Kn for some k . We determine rck ( K 2 □ Kn ) for k = 2, 3, 4 and prove that there exists Cartesian product graphs K 2 □ Kn such that rck ( K 2 □ Kn ) = 3 for each integer k ≥ 2.