The (Strong) Rainbow Connection Number of Join Of Ladder and Trivial Graph

Abstract

Let G = (V,E) be a nontrivial, finite, and connected graph. A function c from E to {1,2,...,k},k ∈ N, can be considered as a rainbow k-coloring if every two vertices x and y in G has an x- y path. Therefore, no two path's edges receive the same color; this condition is called a “rainbow path”. The smallest positive integer k, designated by rc(G), is the G rainbow connection number. Thus, G has a rainbow k-coloring. Meanwhile, the c function is considered as a strong rainbow k-coloring within the condition for every two vertices x and y in G have an x - y rainbow path whose length is the distance between x and y. The smallest positive integer k, such as G, has a strong rainbow k-coloring; such a condition is called a strong rainbow connection number of G, denoted by src(G). In this research, the rainbow connection number and strong rainbow connection number are determined from the graph resulting from the join operation between the ladder graph and the trivial graph, denoted by rc(L_n∨K_1) and src(L_n∨K_1) respectively. So, rc (L_n∨K_1 )= src (L_n∨K_1 )=2,"for" 3≤n≤4 and rc (L_n∨K_1 )=3, while src(L_n∨K_1 )=⌈n/2⌉,"for" n≥5.

Keywords

• rainbow path
• ladder graph
• join
• rainbow connection number