Rainbow Connection in Some Brick Product Graphs

Abstract

Let $G$ be a non-trivial connected graph on which is defined a colouring $c: E(G)\to \{1,2,3,\dots,k\}$, $k\in N$ of edges of $G$, where adjacent edges may be coloured the same. A path $P$ in $G$ is a rainbow path if no two edges of $P$ are coloured the same. $G$ is rainbow-connected if it contains a rainbow $u-v$ path for every two vertices $u$ and $v$ of $G$. The minimum $k$ for which there exists such a $k$-edge colouring is called rainbow connection number of $G$, denoted by $r_{c}(G)$. In this paper we determine $r_{c}(G)$ for some brick product graphs $C(2n,m,r)$ associated with even cycles for $m=2$.