Rainbow connectivity of Moore cages of girth 6

Abstract Let G be an edge-colored graph. A path P of G is said to be rainbow if no two edges of P have the same color. An edge-coloring of G is a rainbow t -coloring if for any two distinct vertices u and v of G there are at least t internally vertex-disjoint rainbow ( u , v ) -paths. The rainbow t -connectivity r c t ( G ) of a graph G is the minimum integer j such that there exists a rainbow t -coloring using j colors. A ( k ; g ) - cage is a k -regular graph of girth g and minimum number of vertices denoted n ( k ; g ) . In this paper we focus on g = 6 . It is known that n ( k ; 6 ) ≥ 2 ( k 2 − k + 1 ) and when n ( k ; 6 ) = 2 ( k 2 − k + 1 ) the ( k ; 6 ) -cage is called a Moore cage. In this paper we prove that the rainbow k -connectivity of a Moore ( k ; 6 ) -cage G satisfies that k ≤ r c k ( G ) ≤ k 2 − k + 1 . It is also proved that the rainbow 3-connectivity of the Heawood graph is 6 or 7.