Bilangan Kromatik Harmonik pada Graf Hasil Kali Kartesian P3 x Sn

Abstract

This research discusses the harmonious chromatic number on the Cartesian product of a path graph with three vertices (P3) and a star graph with n vertices (Sn). Harmonious coloring is a vertex coloring of a graph such that each pair of colors appears on at most one edge. The objective of this research is to develop a harmonious coloring algorithm and also to determine and prove a general formula for the harmonious chromatic number of the graph P3 X Sn. The research method is literature-based with a mathematical approach, start from constructing modified adjacency matrices until testing the coloring algorithm. The proof is conducted through mathematical induction and structural graph analysis. The result shows that the harmonious chromatic number of P3 X Sn for n = 1 is 5, for n = 2,3 is 7, for n = 4 is 8, whereas for n >= 5, it is n + 3.