THE RAINBOW VERTEX CONNECTION NUMBER OF FINGER GRAPHS, MOUNTAIN GRAPHS, AND BOAT GRAPHS

• Main Author: P. (NIM : 20113060), JUNIATI
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/20232
• Institution: Institut Teknologi Bandung

All graphs considered in this thesis are simple and finite. 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 define and determine the rainbow vertex-connection number of three new graph classes, namely finger graphs, mountain graphs, and boat graphs.