Rainbow connectivity of Moore cages of girth 6

摘要

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 rc(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 = rc(k)(G) = k(2) - k + 1. It is also proved that the rainbow 3-connectivity of the Heawood graph is 6 or 7. (C) 2018 Elsevier B.V. All rights reserved.