On Proper (Strong) Rainbow Connection of Graphs

Abstract

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 = Kp1Kpn, where n≥ 1, and p1, . . . , pn>1 are integers, then prc(G) = psrc(G) = χ′(G), where χ′(G) denotes the chromatic index of G. Finally, we investigate some su cient 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.

Keywords

• proper (strong) rainbow connection number
• cartesian product
• chromatic index
• 05c15
• 05c40
• 05c75