PENENTUAN BILANGAN KROMATIK HARMONIK PADA GRAF HASIL KALI KARTESIAN ANTARA GRAF LINTASAN DENGAN TIGA TITIK DAN GRAF BINTANG DENGAN (N+1) TITIK - Feren, Feren; Suwilo, Saib; Mardiningsih, Mardiningsih; Yanti, Maulida (Universitas Islam Sumatera Utara, 2025)
This research discusses the harmonious chromatic number on the Cartesian product of a path graph with three vertices (P_3) and a star graph with n vertices (S_n). 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 P_3×S_n. 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 P_3×S_n for n=1 is 5, for n=2,3 is 7, for n=4 is 8, whereas for n≥5, it is n+3.