On the rainbow coloring for some graph operations

Abstract

Let G = (V, E) be a nontrivial, finite, simple and undirected connected graph on which is defined a coloring f : E(G) → {1,2, …, k}, k ∈ N. The adjacent edges may be colored the same colors. A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph G is rainbow connected if there exists a rainbow u – v path for every two vertices u and v of G. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of k colors required to edge color the graph such that the graph is rainbow connected. In this paper, we determine the exact values of rainbow connection number of some special graph operations, namely cartesian product, tensor product, composition of two special graphs and also amalgamation of special graphs. The result shows that all exact values of rc(G) attain a lower bound of the rainbow connectivity, namely diam(G).