Rainbow and strong rainbow connection number for some families of graphs
Abstract: Let G be a nontrivial connected graph. Then G is called a rainbow connected graph if there exists a coloring c : E(G) → {1, 2, ..., k}, k ∈ N, of the edges of G, such that there is a u − v rainbow path between every two vertices of G, where a path P in G is a rainbow path...
| Authors: | ; ; ; |
|---|---|
| Format: | Article |
| Status: | Published version |
| Publication date: | 2020 |
| Country: | Chile |
| Institution: | Agencia Nacional de Investigación y Desarrollo |
| Repository: | SciELO Chile |
| Language: | English |
| OAI Identifier: | oai:scielo:S0716-09172020000400737 |
| Online Access: | http://www.scielo.cl/scielo.php?script=sci_arttext&pid=S0716-09172020000400737 |
| Access Level: | Open access |
| Keyword: | Edge coloring Rainbow coloring Strong rainbow coloring |
| Summary: | Abstract: Let G be a nontrivial connected graph. Then G is called a rainbow connected graph if there exists a coloring c : E(G) → {1, 2, ..., k}, k ∈ N, of the edges of G, such that there is a u − v rainbow path between every two vertices of G, where a path P in G is a rainbow path if no two edges of P are colored the same. The minimum k for which there exists such a k-edge coloring is the rainbow connection number rc(G) of G. If for every pair u, v of distinct vertices, G contains a rainbow u − v geodesic, then G is called strong rainbow connected. The minimum k for which G is strong rainbow-connected is called the strong rainbow connection number src(G) of G. The exact rc and src of the rotationally symmetric graphs are determined. |
|---|