On proper (strong) rainbow connection of graphs
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.
- On the strong rainbow connection of a graph
- Proper rainbow connection number of graphs
- On proper-path colorings in graphs
- Rainbow connectivity and proper rainbow connectivity of \(\theta(1,s,t)\)
- scientific article; zbMATH DE number 7144826 (Why is no real title available?)
- (Strong) proper vertex connection of some digraphs
This page was built for publication: On proper (strong) rainbow connection of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2227108)
