UNEJ e-Proceeding
2016: Proceeding The 1st International Basic Science Conference

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

Gembong A. W. (Mathematics Depart. University of Jember)
Dafik Dafik (CGANT, University of Jember
Mathematics Edu. Depart. University of Jember)

Ika Hesti Agustin (CGANT, University of Jember
Mathematics Depart. University of Jember)

Slamin Slamin (CGANT, University of Jember
Information System Depart. University of Jember)



Article Info

Publish Date
08 Aug 2017

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.

Copyrights © 2016