Rainbow Connection Numbers of Ladders and Möbius Ladders

Abstract

A path in an edge-colored graph is said to be a rainbow path if no two edges on the path share the same color. An edge-colored graph $G$ is rainbow connected if there exists a $u-v$ rainbow path for any two vertices $u$ and $v$ in $G$. The rainbow connection number of a graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. For any two vertices $u$ and $v$ of $G$, a rainbow $u-v$ geodesic in $G$ is a rainbow $u$–$v$ path of length $d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. The graph $G$ is strongly rainbow connected if there exists a rainbow $u-v$ geodesic for any two vertices $u$ and $v$ in $G$. The strong rainbow connection number of $G$, denoted by $src(G)$, is the smallest number of colors that are needed in order to make $G$ strongly rainbow connected.

In this paper, we determine the precise (strong) rainbow connection numbers of ladders and Möbius ladders. Let $p$ be an odd prime; we show the (strong) rainbow connection numbers of Cayley graphs on the dihedral group $D_{2p}$ of order $2p$ and the cyclic group ${\mathbb{Z}}_{2p}$ of order $2p$. In particular, an open problem posed by Li et al. in [8] is solved.