(Strong) Rainbow Vertex-Connection Number pada Graf Hasil Operasi Perkalian Kartesian Graf Bintang dan Graf Cycle;

Abstract

A rainbow vertex path is a path that connects two distinct vertices in a graph, where all its internal vertices have distinct colors. The rainbow vertex-connection number is the minimum number of colors used such that every pair of vertices is connected by at least one rainbow vertex path, denoted by 𝑟𝑣𝑐(𝐺). A geodesic rainbow vertex path 𝑢 −𝑣 is a path with a length of 𝑑(𝑢,𝑣). A graph 𝐺 is said to be strongly rainbow vertex-connected if every pair of distinct vertices is connected by at least one geodesic rainbow vertex path. The number of colors required to make a graph strongly rainbow vertex-connected is called the strong rainbow vertex-connection number, denoted by 𝑠𝑟𝑣𝑐(𝐺). The Cartesian product of two graphs, denoted by � �□𝐻, is defined as a graph whose vertex set is 𝑉(𝐺) × 𝑉(𝐻), where two vertices (𝑢, 𝑣) and (𝑥,𝑦) are adjacent if and only if 𝑢 = 𝑥 and 𝑣𝑦 ∈ 𝐸(𝐻); or 𝑣 = 𝑦 and � �𝑥 ∈ 𝐸(𝐺). In this study, star graphs and cycle graphs are used. A star graph is a simple and connected graph that has 𝑛 + 1 vertices, with one central vertex of degree 𝑛 that is adjacent to 𝑛 leaf vertices. The star graph is denoted by 𝑆𝑛, with � � ≥2. Meanwhile, a cycle graph is a simple and connected graph which each vertex has degree two, denoted by 𝐶𝑚 with 𝑚 ≥ 3. Based on the results of this study, the strong rainbow vertex-connection number of the graph 𝑆𝑛□𝐶𝑚 is � �𝑟𝑣𝑐(𝑆𝑛□𝐶𝑚) = 𝑚 2 +1, for 𝑚 even and 𝑠𝑟𝑣𝑐(𝑆𝑛□𝐶𝑚) = 𝑚+1 for 𝑚 odd. This study also found that if a graph 𝐺 has 𝑠𝑟𝑣𝑐(𝐺) = 𝑑𝑖𝑎𝑚(𝐺) − 1, then 𝑟𝑣𝑐(𝐺) = 𝑠𝑟𝑣𝑐(𝐺).