Let G be a connected graph with [Formula presented]. The rainbow connection number rc(G) is the smallest k for which there is a map [Formula presented] such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition [Formula presented] is obtained by replacing each vi with the graph Hi. We prove [Formula presented] if each Hi has at least diam(G)≥4 vertices, improving known upper bounds of Basavaraju et al. and Gologranc et al. (2014). We prove the same result when diam(G) = 3 but with some additional conditions. When diam(G) = 2, we show that the largest possible value of [Formula presented] is related to whether every vertex of G is contained in a triangle or not.
|Journal||AKCE International Journal of Graphs and Combinatorics|
|Publication status||Accepted/In press - 1 Jan 2018|
- Lexicographic product
- Rainbow connection