PENENTUAN BILANGAN KROMATIK HARMONIK PADA GRAF HASIL KALI KARTESIAN ANTARA GRAF LINTASAN DENGAN TIGA TITIK DAN GRAF BINTANG DENGAN (N+1) TITIK

Feren Feren, Saib Suwilo, Mardiningsih Mardiningsih, Maulida Yanti

Abstract


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.

Keywords


graf lintasan; graf bintang; graf hasil kali Kartesian; pewarnaan harmonik; bilangan kromatik harmonik

References


Afriantini, Helmi, & Fran, F. (2019). Pewarnaan Simpul, Sisi, Wilayah pada Graf dan Penerapannya. Bimaster, 8, 773–782.

Asy'ari, M. L., Dafik, Agustin, I. H., Nisviasari, R., & Adawiyah, R. (2022). On Graceful Chromatic Number of Some Graphs. Journal of Physics: Conference Series, 2157, 1–10.

Chartrand, G., & Zhang, P. (2012). A First Course in Graph Theory. New York: Dover Publications.

Edwards, K. J. (2013). Harmonious Chromatic Number of Directed Graphs. Discrete Applied Mathematics, 161, 369–376.

Fran, F., Kusumastuti, N., & Robiandi. (2023). Bilangan Kromatik Harmonis pada Graf Payung, Graf Parasut, dan Graf Semi Parasut. Jurnal Matematika, Sains, dan Teknologi, 24, 15–22.

Gross, J. L., Yellen, J., & Zhang, P. (2014). Handbook of Graph Theory (2nd ed.). USA: CRC Press.

Imrich, W. & Klavzar, S. (2000). Product Graphs: Structure and Recognition. New Jersey: Wiley-Interscience.

Irawati, D. (2013). Pelabelan Total Sisi Ajaib pada Graf Bintang. Jurnal Matematika UNAND, 2, 85–89.

Leon, S. J. (2015). Linear Algebra with Applications (9th ed.). England: Pearson Education Limited.

Lestari, D. D. A., Kristiana, A. I., Prihandini, R. M., Alfarisi, R., Setiawan, T. B., & Adawiyah, R. (2024). Bilangan Kromatik Graceful pada Keluarga Graf Sentripetal. Jurnal Diferensial, 6, 57–64.

Rahayuningsih, S. (2018). Teori Graph dan Penerapannya. Malang: Universitas Wisnuwardhana Press Malang.

Retnoningsih, I. I., Dafik, & Hussen, S. (2022). Pewarnaan Titik pada Keluarga Graf Sentripetal. Journal of Mathematics and Applications, 3.

Robiandi, Kusumastuti, N., & Fran, F. (2021). Pewarnaan Harmonis pada Graf Lili dan Graf Pertemanan. Bimaster, 10, 317–322.

Selinger, P. (2018). Matrix Theory and Linear Algebra. Washington, DC: The Saylor Foundation’s Open Textbook Challenge.

Sholikha, S.M., & Rahadjeng, B. (2014). Pewarnaan Harmonis Graf Garis, Graf Middle dan Graf Central dari Keluarga Graf Bintang Ganda. MATHunesa, 3, 93-97.

Vivin, V. J., & Ali, A. M. M. (2009). On Harmonious Coloring of Middle Graph of C(Cₙ), C(K₁,ₙ), and C(Pₙ). Note di Matematica, 29, 201–211.




DOI: https://doi.org/10.30743/mes.v11i1.11405

Refbacks

  • There are currently no refbacks.