On the Rainbow Vertex Connection Number of Edge Comb of Some Graph

Agustina M.; Dafik Dafik; Slamin Slamin; Kusbudiono Kusbudiono

Agustina M. CGANT University of Jember Indonesia; Mathematics Depart. University of Jember Indonesia
Dafik Dafik CGANT University of Jember Indonesia; Mathematics Edu. Depart. University of Jember Indonesia
Slamin Slamin CGANT University of Jember Indonesia; System Information. Depart. University of Jember
Kusbudiono Kusbudiono CGANT University of Jember Indonesia; Mathematics Depart. University of Jember Indonesia

Abstract

By an edge comb, we mean a graph formed by combining two graphs G and H, where each edge of graph G is replaced by the which one edge of graph H, denote by G D H. A vertex colored graph G D H = (V (G D H);E(G D H)) is said rainbow vertex-connected, if for every two vertices u and v in V (G D H), there is a u 􀀀 v path with all internal vertices have distinct color. The rainbow vertex connection number of G D H, denoted by rvc(G D H) is the smallest number of color needed in order to make G D H rainbow vertex-connected. This research aims to find an exact value of the rainbow vertex connection number of exponential graph, namely rvc(G D H) when G D H are Pn D Btm, Sn D Btm, Ln D Btm, Fm;n D Btp, rvc(Pn D Sm), rvc(Cn D Sm), and rvc(Wn D Sm) Wn D Btm. The result shows that the resulting rainbow vertex connection attain the given lower bound.