# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

# Discussiones Mathematicae Graph Theory

Article in press

Authors:

H. Jiang, W. Li, X. Li, C. Magnant

Title:

On proper (strong) rainbow connection of graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-07-23, Revised: 2019-01-09, Accepted: 2019-01-09, https://doi.org/10.7151/dmgt.2201

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=K_{p_1}\Box \cdots \Box K_{p_n}$, where $n\geq1$, and $p_1,\dots,p_n>1$ are integers, then $prc(G)=psrc(G)=\chi'(G)$, where $\chi'(G)$ denotes the chromatic index of $G$. Finally, we investigate some sufficient 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