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.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.