Rainbow connection number of generalized composition
Let be a connected graph with . The rainbow connection number is the smallest for which there is a map such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition is obtained by replacing each with the graph . We prove if each has at least ve...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2018.10.001 |
| Summary: | Let be a connected graph with . The rainbow connection number is the smallest for which there is a map such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition is obtained by replacing each with the graph . We prove if each has at least vertices, improving known upper bounds of Basavaraju et al. and Gologranc et al. (2014). We prove the same result when but with some additional conditions. When , we show that the largest possible value of is related to whether every vertex of is contained in a triangle or not. |
|---|---|
| ISSN: | 0972-8600 2543-3474 |