Kathy McKeon, Connecticut College, Department of Mathematics, 270 Mohegan Avenue, Box 5561, New London, CT 06320, USA; Garry L. Johns, Saginaw Valley State University, University Center, Department of Mathematical Sciences, MI 48710-0001, USA; Ping Zhang, Gary Chartrand, Western Michigan University, Department of Mathematics, Kalamazoo, MI 49008, USA, e-mail: ping.zhang@wmich.edu
Abstract: Let $G$ be a nontrivial connected graph on which is defined a coloring $c E(G) \rightarrow\{1, 2, \ldots, k\}$, $k \in\bbN$, of the edges of $G$, where adjacent edges may be colored the same. A path $P$ in $G$ is a rainbow path if no two edges of $P$ are colored the same. The graph $G$ is rainbow-connected if $G$ 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 coloring is the rainbow connection number $\rc(G)$ of $G$. If for every pair $u, v$ of distinct vertices, $G$ contains a rainbow $u-v$ geodesic, then $G$ is strongly rainbow-connected. The minimum $k$ for which there exists a $k$-edge coloring of $G$ that results in a strongly rainbow-connected graph is called the strong rainbow connection number $\src(G)$ of $G$. Thus $\rc(G) \le\src(G)$ for every nontrivial connected graph $G$. Both $\rc(G)$ and $\src(G)$ are determined for all complete multipartite graphs $G$ as well as other classes of graphs. For every pair $a, b$ of integers with $a \ge3$ and $b \ge(5a-6)/3$, it is shown that there exists a connected graph $G$ such that $\rc(G)=a$ and $\src(G)=b$.
Keywords: edge coloring, rainbow coloring, strong rainbow coloring
Classification (MSC2000): 05C15, 05C38, 05C40
Full text of the article: