The Rainbow (1,2)-Connection Number of Exponential Graph and It’s Lower Bound

Abstract

Let G = (V, E) be a simple, nontrivial, finite, connected and undirected graph. Let c be a coloring c : E(G) → {1, 2, . . . , k}, k ∈ N. 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. Furthermore, for an l-connected graph G and an integer k with 1 ≤ k ≤ l, the rainbow k-connection number rck(G) of G is defined to be the minimum number of colors required to color the edges of G such that every two distinct vertices of G are connected by at least k internally disjoint rainbow paths. In this paper, we determine the exact values of rainbow connection number of exponential graphs, namely Path of ladder as exponent, Cycle of Ladder as exponent, Cycle of Triangular Ladder as exponent, Cycle of Complete as exponent. We also proved that rc2(G) = diam(G) + 1.