THE RAINBOW VERTEX CONNECTION NUMBER OF FINGER GRAPHS, MOUNTAIN GRAPHS, AND BOAT GRAPHS - P. (NIM : 20113060), JUNIATI
All graphs considered in this thesis are simple and ﬁnite. Let G = (V (G),E(G)) be a nontrivial connected graph and k be a positive integer. Let c : V (G) → {1,2,...,k} be a k−coloring of the vertices of G. A path of G is said a rainbow vertex-path if whose internal vertices have distinct colors. A vertex-colored graph is said rainbow vertex-connected if for any two vertices are connected by at least one rainbow vertex-path. The rainbow vertex-connection number of a connected graph, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. Let n be the order of G, Krivelevich and Yuster showed that diam(G)−1 ≤ rvc(G) ≤ n−2. If G consists of q cut vertices, then rvc(G) ≥ q. In this thesis we deﬁne and determine the rainbow vertex-connection number of three new graph classes, namely ﬁnger graphs, mountain graphs, and boat graphs.