THE RAINBOW VERTEX CONNECTION NUMBER OF m-SHADOW GRAPH
Mohamad Fahruli Wahyujati (1,a), M. Salman A. N (2,b), Alfiatri Arif Susilo (2,c).

(1) Mathematics Department Universitas Gadjah Mada, Yogyakarta Indonesia.
(2) Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jl. Ganesa No. 10 Bandung 40132, Indonesia.

a) fahruliwahyujati[at]gmail.com
b) Corresponding author: msalman[at]math.itb.ac.id
c) alfiatrias[at]students.itb.ac.id

Abstract

For any simple connected graph G=(V(G),E(G)) on vertex-coloring is called rainbow vertex-connected graph if any two vertices are connected by a path whose all internal vertices have different color. Such a path is called rainbow vertex-path. The rainbow vertex-connection number, denoted by rvc(G), is the smallest number of colors needed such that G is rainbow vertex-connected.

For a graph G on n vertices with V(G)=\{v_1,v_2,\ldots,v_n\}, the m-shadow graph D_m(G) of G is obtained by taking m-copies of G, say G_1, G_2,...,G_m, then adding 2(m-1). |E(G)| new edges by joining each vertex u in G_i to the neighbors of the corresponding vertex u in G_{i+1}, 1\leq i \leq m-1.


In this paper, we determine the lower and upper bounds of the rainbow vertex connection number of m-shadow graph and present the exact values of rainbow vertex connection number of particular class of graph, such graph on diameter 2, complete graph and cycle graph.

Keywords: Rainbow Coloring, Rainbow Vertex Coloring, Rainbow Vertex Connection Number, m-Shadow Graph

Topic: MATHEMATICS AND STATISTICS