On proper (strong) rainbow connection of graphs (Q2227108): Difference between revisions

In this paper, the authors consider finite, undirected graphs without loops or parallel edges. Let \(G=(V, E)\) be a graph. A mapping \(c:E\rightarrow \{1,\dots,t\}\) is a proper \(t\)-edge-coloring, if adjacent edges of \(G\) receive different colors. A path \(P\) of \(G\) is an R-path with respect to \(c\), if any two edges of \(P\) have different colors. For a graph \(G\) let \(\operatorname{prc}(G)\) be the smallest \(t\), such that \(G\) admits a \(t\)-edge-coloring with the property that for any two different vertices \(u\) and \(v\) of \(G\) there is an R-path connecting \(u\) and \(v\). Moreover, let \(\operatorname{psrc}(G)\) be the smallest \(t\), such that \(G\) admits a \(t\)-edge-coloring with the property that for any two different vertices \(u\) and \(v\) of \(G\) there is an R-path connecting \(u\) and \(v\) that is a shortest \(u\)-\(v\)-path. In this paper, the authors characterize the graphs \(G\) with \(\operatorname{prc}(G)=|E|\) or \(\operatorname{prc}(G)=|E|-1\). Then they show that for any \(n\geq 1\) and \(p_1,\dots,p_n\geq 2\), the Cartesian product of \(K_{p_1},\dots,K_{p_n}\), denoted by \(G\), satisfies \(\operatorname{prc}(G)=\operatorname{psrc}(G)=\chi^\prime(G)\). Here \(\chi^\prime(G)\) is the chromatic index of \(G\). In the end of the paper, the authors present some sufficient conditions for a graph \(H\) to satisfy \(\operatorname{prc}(H)=\operatorname{rc}(H)\). Here, \(\operatorname{rc}(H)\) denotes the smallest \(t\) for which there is a mapping \(c:E(H)\rightarrow \{1,\dots,t\}\) (not necessarily a proper edge-coloring) such that for any two distinct vertices of \(H\) there is an R-path connecting these two vertices.