Bilangan Terhubung Titik Pelangi pada Graf Garis dan Graf Tengah dari Hasil Operasi Comb Graf Bintang C3 dan Graf Bintang Sn
Downloads
How to Cite
Penelitian ini bertujuan menentukan bilangan terhubung titik pelangi (rainbow vertex connection number) pada graf garis dan graf tengah yang diperoleh dari hasil operasi comb antara graf lingkaran dan graf bintang , dengan . Penelitian ini merupakan kajian teoretis dengan pendekatan studi literatur melalui analisis konsep teori graf, operasi comb, graf garis, graf tengah, serta pewarnaan titik pelangi. Penentuan nilai bilangan terhubung titik pelangi dilakukan dengan menganalisis struktur graf, menentukan diameter graf, mengonstruksi fungsi pewarnaan titik, dan memverifikasi keberadaan lintasan titik pelangi untuk setiap pasangan titik. Hasil penelitian menunjukkan bahwa bilangan terhubung titik pelangi pada graf garis adalah . Sementara itu, pada graf tengah , diperoleh . Hasil ini menunjukkan bahwa transformasi graf hasil operasi comb ke dalam bentuk graf garis dan graf tengah menghasilkan kebutuhan warna yang berbeda. Temuan ini memberikan kontribusi terhadap pengembangan kajian pewarnaan pelangi, khususnya pada graf hasil operasi dan graf hasil transformasi.
Rainbow Vertex Connection Number of the Line Graph and the Middle Graph of the Comb Operation on the Star Graph C3 and the Star Graph Sn
Abstract
This study aims to determine the rainbow vertex connection number of the line graph and the middle graph obtained from the comb operation between the cycle graph and the star graph , where . This research is a theoretical study using a literature-based approach through the analysis of graph theory concepts, comb operation, line graph, middle graph, and rainbow vertex coloring. The determination of the rainbow vertex connection number was carried out by analyzing the graph structure, determining the graph diameter, constructing a vertex-coloring function, and verifying the existence of rainbow vertex paths for each pair of vertices. The results show that the rainbow vertex connection number of the line graph is . Meanwhile, for the middle graph , it is obtained that . These results indicate that transforming the graph obtained from the comb operation into its line graph and middle graph produces different coloring requirements. The findings contribute to the development of rainbow coloring studies, particularly on graphs resulting from graph operations and graph transformations.
Abdurahman, M., Helmi, H., & Fran, F. (2024). Bilangan Kromatik Permainan Graf Ubur-Ubur, Graf Siput, dan Graf Gurita. Jambura Journal of Mathematics, 6(1). https://doi.org/10.37905/jjom.v6i1.23958
Akadji, A. F., Taha, D., Lakisa, N., dan Yahya, N. I. 2019. Bilangan terhubung titik pelangi pada amalgamasi graf berlian. Euler: Jurnal Ilmiah Matematika, Sains dan Teknologi, 7(2):56–61. doi:10.34312/euler.v7i2.10345
Annadhifi, M. I. N., Adawiyah, R., Dafik, D., & Suparta, I. N. (2024a). Rainbow Vertex Connection Number Of Bull Graph, Net Graph, Triangular Ladder Graph, And Composition Graph (P_n [P_1 ]). Barekeng Jurnal Ilmu Matematika Dan Terapan, 18(3), 1665–1672. https://doi.org/10.30598/barekengvol18iss3pp1665-1672
Arizmendi, O., Hasebe, T., & Lehner, F. (2024). Cyclic independence: Boolean and monotone. Algebraic Combinatorics, 6(6), 1697–1734. https://doi.org/10.5802/alco.309
Babiński, S., Grzesik, A., & Prorok, M. (2025). Directed Graphs Without Rainbow Triangles. Journal of Graph Theory, 109(3), 269–281. https://doi.org/10.1002/jgt.23224
Batiha, I. M., Anakira, N., Hashim, A. Y. B., & Mohamed, B. (2024). A special graph for the connected metric dimension of graphs. Mathematical Models in Engineering, 10(3), 193–201. https://doi.org/10.21595/mme.2024.24176
Borzechowski, M., & Weber, S. (2025). On Flipping Edge Sets in Unique Sink Orientations. Graphs and Combinatorics, 41(3). https://doi.org/10.1007/s00373-025-02929-2
Bowtell, C., Morris, P., Pehova, Y., & Staden, K. (2025). Universality for transversal Hamilton cycles. Bulletin of the London Mathematical Society, 57(3), 711–729. https://doi.org/10.1112/blms.13223
Cairncross, E., Mizgerd, C., & Mubayi, D. (2025). Inducibility of rainbow graphs. Mathematical Proceedings of the Cambridge Philosophical Society, 180(1), 191–218. https://doi.org/10.1017/s0305004125101692
Chartrand, G., Johns, G., McKeon, K., & Zhang, P. (2008). Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98.
Dai, T., & Kelly, T. (2025). On the existence of reflecting n-queens configurations. Forum of Mathematics Sigma, 13. https://doi.org/10.1017/fms.2025.10097
Darmadi, D., & Fathurrahman, F. (2025). Identification of Phenotypic Nature of Rainbow Corn (Zea mays L.) Due to Colchicine Treatment. Iop Conference Series Earth and Environmental Science, 1478(1), 012002. https://doi.org/10.1088/1755-1315/1478/1/012002
Darmajid, D., Hidayat, N., Wicaksono, W. B., & Musyarrofah, A. F. (2024). Indeks Wiener dari Graf Identitas dan Graf Pangkat pada Grup Siklis Berhingga. Syntax Literate Jurnal Ilmiah Indonesia, 9(7), 3848–3855. https://doi.org/10.36418/syntax-literate.v9i7.16994
Gupta, C. (2025). Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs. https://doi.org/10.48550/arxiv.2511.21217
Hadiputra, F. F., & Maryati, T. K. (2024). A note on local edge antimagic chromatic number of graphs. Proyecciones (Antofagasta), 43(2), 447–458. https://doi.org/10.22199/issn.0717-6279-6014
Imran, M., Cancan, M., Nadeem, M. F., & Ali, Y. (2024). Further results on edge irregularity strength of some graphs. Proyecciones (Antofagasta), 43(1), 133–151. https://doi.org/10.22199/issn.0717-6279-6175
Kristiana, A. I., & Saputra, G. (2024). Pewarnaan Titik Ketakteraturan Lokal Graf Pensil. Jurnal Axioma Jurnal Matematika Dan Pembelajaran, 9(1), 97–105. https://doi.org/10.56013/axi.v9i1.2492
Krivelevich, M. dan Yuster, R. 2009. The rainbow connection of a graph is (at most) reciprocal to its minimum degree. Journal of Graph Theory, 63(3):185–191. doi:10.1002/jgt.20418.
Kusuma, Y. J. dan Prasetyo, D. A. B. 2020. Pelabelan total tak-ajaib sisi pada multistar. EPSILON: JURNAL MATEMATIKA MURNI DAN TERAPAN, 14(2):62–70.
Li, X. (2025). Constrained Ramsey numbers for rainbow $P_5$. https://doi.org/10.48550/arxiv.2510.18243
Lihawa, I., Ismail, S., Hasan, I. K., Yahya, L., Nasib, S. K., dan Yahya, N. I. 2022. Bilangan terhubung titik pelangi pada graf hasil operasi korona graf prisma (pm,2) dan graf lintasan (p3). Jambura Journal of Mathematics, 4(1):145–151. doi:10.34312/jjom.v4i1.11826.
Listiyaningrum, O. (2025). Graph Coloring Application with Modified Tabu Search Algorithm in School Scheduling. 27, 854–865. https://doi.org/10.4028/p-zdxab3
Nuryatma, N. (2024). Aplikasi Pewarnaan Graf untuk Optimalisasi Distribusi Beras di Badan Usaha Logistik (BULOG ) Kota Samarinda. Basis Jurnal Ilmiah Matematika, 3(1), 38–53. https://doi.org/10.30872/basis.v3i1.1135
Taha, D., Nurwan, N., Nasib, S. K., dan Yahya, N. Y. 2021. Titik bunga dan oleander. UNNES Journal of Mathematics, 10:1–6.
Thamizhendhi, E. al. G. (2024). Some Results on Odd-Even Congruence Labeling of Graphs. Cana, 31(1), 141–149. https://doi.org/10.52783/cana.v31.369
Tonis, M., Zaky, A., Bisra, M., & Suryandartiwi, W. (2025). Perancangan Aplikasi Penjadwalan Praktek Dokter di Rumah Sakit Menggunakan Metode Pewarnaan Graf. Journal of Health, 11(2), 182–189. https://doi.org/10.30590/joh.v11n2.845
Umilasari, R. dan Darmaji. 2015. Bilangan dominasi jarak dua pada graf-graf hasil operasi korona dan comb. justindo, 2(1).
Wang, F., & Hsu, C.-J. (2024). Rainbow Connection Numbers of WK-Recursive Networks and WK-Recursive Pyramids. Mathematics, 12(7), 944. https://doi.org/10.3390/math12070944
Wang, L., Liu, S., & Jiang, H. (2024). Rainbow connections of bioriented graphs. Heliyon, 10(10), e31426. https://doi.org/10.1016/j.heliyon.2024.e31426
Yahya, N. I., Fatmawati, A., Nurwan, N., dan Nasib, S. K. 2023. Rainbow Vertex-Connection Number on Comb Product Operation of Cycle Graph (C_4) and Complete Bipartite Graph (K_3,N). BAREKENG: Jurnal Ilmu Matematika dan Terapan, 17(2):0673–0684. doi:10.30598/barekengvol17iss2pp0673-0684.
Yusak, M. Y., Putri, D. F., & Syaripuddin, S. (2024). Penerapan Pewarnaan Graf Menggunakan Algoritma Welch-Powell pada Penjadwalan Mata Pelajaran. Journal of Mathematics Education and Science, 7(2), 177–183. https://doi.org/10.32665/james.v7i2.2272
Copyright (c) 2026 Abdul Halim Antula, Nurwan Nurwan, Nisky Imansyah Yahya, Emli Rahmi, Armayani Arsal
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with Empiricism Journal agree to the following terms:
- For all articles published in Empiricism Journal, copyright is retained by the authors. Authors give permission to the publisher to announce the work with conditions. When the manuscript is accepted for publication, the authors agrees to implement a non-exclusive transfer of publishing rights to the journals.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-ShareAlike 4.0 International License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
