The (strong) rainbow connection numbers of Cayley graphs of Abelian groups

Hengzhe Li, Xueliang Li, Sujuan Liu

Published 2010-11-03, updated 2010-12-03Version 3

A path in an edge-colored graph $G$, where adjacent edges may have the same color, is called a rainbow path if no two edges of the path are colored the same. The rainbow connection number $rc(G)$ of $G$ is the minimum integer $i$ for which there exists an $i$-edge-coloring of $G$ such that every two distinct vertices of $G$ are connected by a rainbow path. The strong rainbow connection number $src(G)$ of $G$ is the minimum integer $i$ for which there exists an $i$-edge-coloring of $G$ such that every two distinct vertices $u$ and $v$ of $G$ are connected by a rainbow path of length $d(u,v)$. In this paper, we give upper and lower bounds of the (strong) rainbow connection Cayley graphs of Abelian groups. Moreover, we determine the (strong) rainbow connection numbers of some special cases.