On the Rainbow Connectivity of Cages

摘要

A path Q in an edge-colored graph is a rainbow path if no two edges of Q are assigned the same color. The rainbow connectivity K_r(G) of a graph G with connectivity k ≥ 1 is the minimum number of colors needed in an edge-coloring (not necessarily a proper edge-coloring) of G such that every two vertices u and v of G are connected by at least k internally disjoint u - v rainbow paths. The rainbow connectivity of small cages is discussed. It is shown that the rainbow connectivity of the Petersen graph is 5.