Note on the Rainbow \(k\)-Connectivity of Regular Complete Bipartite Graphs

Abstract

A path in an edge-colored graph \(G\), where adjacent edges may be colored the same, is called a rainbow path if no two edges of the path are colored the same. For a \(k\)-connected graph \(G\) and an integer \(k\) with \(1 \leq k \leq \kappa\), the rainbow \(k\)-connectivity \(rc_k(G)\) of \(G\) is defined as the minimum integer \(j\) for which there exists a \(j\)-edge-coloring of \(G\) such that any two distinct vertices of \(G\) are connected by \(k\) internally disjoint rainbow paths. Denote by \(K_{r,r}\) an \(r\)-regular complete bipartite graph. Chartrand et al. in in “G. Chartrand, G.L. Johns, K.A.McKeon, P. Zhang, The rainbow connectivity of a graph, Networks \(54(2009), 75-81”\) left an open question of determining an integer \(g(k)\) for which the rainbow \(k\)-connectivity of \(K_{r,r}\) is \(3\) for every integer \(r \geq g(k)\). This short note is to solve this question by showing that \(rc_k(K_{r,r}) = 3\) for every integer \(r \geq 2k\lceil\frac{k}{2}\rceil\), where \(k \geq 2\) is a positive integer.