On Proper (Strong) Rainbow Connection of Graphs

Jiang, Hui ; Li, Wenjing ; Li, Xueliang ; Magnant, Colton

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 469-479

Résumé

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… K_pn, where n≥ 1, and p_1, . . ., p_n gt;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.

Détail

Keywords: proper (strong) rainbow connection number, Cartesian product, chromatic index