On proper (strong) rainbow connection of graphs (Q2227108): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Xue Liang Li / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Vahan V. Mkrtchyan / rank | |||
Normal rank |
Revision as of 05:34, 14 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On proper (strong) rainbow connection of graphs |
scientific article |
Statements
On proper (strong) rainbow connection of graphs (English)
0 references
10 February 2021
0 references
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.
0 references
edge-coloring
0 references
path
0 references
Cartesian product
0 references
complete graph
0 references