On Proper (Strong) Rainbow Connection of Graphs

A path in an edge-colored graph $G$ is called a rainbow path if no two edges on the path have the same color. The graph $G$ is called rainbow connected if between every pair of distinct vertices of $G$, there is a rainbow path. Recently, Johnson et al. considered this concept with the additional requirement that the coloring of $G$ is proper. The proper rainbow connection number of $G$, denoted by $prc(G)$, is the minimum number of colors needed to properly color the edges of $G$ so that $G$ is rainbow connected. Similarly, the proper strong rainbow connection number of $G$, denoted by $psrc(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that for any two distinct vertices of $G$, there is a rainbow geodesic (shortest path) connecting them. In this paper, we characterize those graphs with proper rainbow connection numbers equal to the size or within 1 of the size. Moreover, we completely solve a question proposed by Johnson et al. by proving that if \(G = K_{p1} \Box \dots \Box K_{pn}\), where $n≥ 1$, and $p_1, . . ., p_n>1$ are integers, then $prc(G) = psrc(G) = χ^′(G)$, where $χ^′(G)$ denotes the chromatic index of $G$. Finally, we investigate some suffcient conditions for a graph $G$ to satisfy $prc(G) = rc(G)$, and make some slightly positive progress by using a relation between $rc(G)$ and the girth of the graph.