Pelabelan L(2,1) pada Beberapa Kelas Graf Pohon

Authors

  • Hafif Komarullah Tadris Matematika, Universitas Al-Falah As-Sunniyah, Kencong-Jember
  • Mifdati Afifah Tadris Matematika, Universitas Al Falah As Sunniyah
  • Pudji Rahmawati Tadris Matematika, Universitas Al Falah As Sunniyah

Keywords:

Pelabelan graf, Pelabelan L(2,1), Nilai minimum span

Abstract

Teori graf telah mengalami perkembangan sejak pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736. Salah satu topik yang terus diteliti adalah pelabelan graf. Pelabelan graf merupakan sebuah pemetaan elemen graf ke bilangan bulat dengan aturan-aturan tertentu. Terdapat tiga jenis pelabelan graf yang dibedakan menurut domainnya, yaitu pelabelan titik (dengan domain berupa titik), pelabelan sisi (dengan domain berupa sisi), dan pelabelan total (dengan domain yang mencakup titik dan sisi). Pelabelan L(2,1) merupakan salah satu tipe pelabelan titik yang didefinisikan sebagai fungsi yang memetakan titik-titik dalam graf dengan bilangan bulat non-negatif, dengan ketentuan bahwa untuk setiap dua titik yang terpisah oleh jarak satu, selisih labelnya harus minimal dua, dan untuk setiap dua titik yang terpisah oleh jarak dua, selisih labelnya harus minimal satu. Konsep pelabelan L(2,1) berfokus pada penentuan nilai minimum dari label terbesar (nilai minimum span) yang dilambangkan dengan λ_2,1. Dalam makalah ini peneliti menganalisis nilai minimum span pada beberapa kelas graf pohon. Metode yang peneliti gunakan untuk mendapatkan nilai minimum span adalah studi literatur, deskriptif aksiomatik, dan pendeteksian pola.

References

Aminulloh, M., & Afif, R. (2019). Minimal label terbesar dari pelabelan titik dan sisi L (2, 1) pada graf petersen P (n, 1) (Doctoral dissertation, Universitas Islam Negeri Maulana Malik Ibrahim).

Budayasa, K. (2007). Teori Graph dan Aplikasinya. Unesa University Press, Surabaya.

Chartrand, G. (1977). Introductory Graph Theory. Dover, New York.

Fatimah, S., Sudarsana, I. W., & Musdalifah, S. (2016). Pelabelan L (2, 1) pada Operasi Beberapa Kelas Graf. Jurnal Ilmiah Matematika dan Terapan, 13(2). https://core.ac.uk/reader/290089130

Gallian, J. A. (2022). A Dynamic Survey of Graph Labeling. Electronic Journal of Combinatorics, 6(25), 4-623. Article DS6. https://doi.org/10.37236/11668

Griggs, J. R., & Yeh, R. K. (1992). Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4), 586-595. https://doi.org/10.1137/0405048

Hale, W. K. (1980). Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12), 1497-1514. https://doi.org/10.1109/PROC.1980.11899

Halikin, I., & Komarullah, H. (2022, February). Labelling of Generalized Friendship, Windmill, and Torch Graphs with a Condition at Distance Two. In International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021) (pp. 35-39). Atlantis Press. https://doi.org/10.2991/acsr.k.220202.008

Julaeha, S., Luspitasari, I., & Sukaesih, E. (2017). Pelabelan Total Tak Teratur Total pada Graf Bunga. Jurnal Istek, 10(1), 83-101.

https://journal.uinsgd.ac.id/index.php/istek/article/view/1458/1021

Komarullah, H. (2023, December). Nilai Minimum Span pada Graf Gurita, Graf Siput, dan Graf Ubur-Ubur. In Prossiding Galuh Mathematics National Conference (Vol. 3, No. 1, pp. 56-62). https://jurnal.unigal.ac.id/GAMMA-NC/article/view/12952/6999

Komarullah, H., Halikin, I., & Santoso, K. A. (2022, February). On the minimum span of cone, tadpole, and barbell graphs. In International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021) (pp. 40-43). Atlantis Press. https://doi.org/10.2991/acsr.k.220202.009

Komarullah, H., Slamin., & Wijaya, K. (2022, February). A Minimum Coprime Number for Amalgamation of Wheel. In International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021) (pp. 53-57). Atlantis Press. https://doi.org/doi:10.2991/acsr.k.220202.012

Kumar, A., & Vats, A. K. (2020). Application of graph Labeling in Crystallography. Proc. Mater. Today. 1-5. https://doi.org/10.1016/j.matpr.2020.09.371

Lum, A. (2007). Upper Bound on L(2,1)-labelling Number of Graphs with Maximum Degree Δ. Retrieved from https://www.whitman.edu/documents/academics/mathematics/lumaa.pdf

Prasanna, N. L., Sravanthi, K., & Sudhakar, N. (2014). Applications of graph labeling in communication networks. Oriental Journal of Computer Science and Technology, 7(1), 139-145. http://www.computerscijournal.org/pdf/vol7no1/OJCSV07I1P139-145.pdf

Prihandoko, A. C., Dafik, D., & Agustin, I. H. (2019). Implementation of super H-antimagic total graph on establishing stream cipher. Indonesian Journal of Combinatorics, 3(1), 14-23. http://dx.doi.org/10.19184/ijc.2019.3.1.2

Sagala, Y., & Susiana. (2017). Pelabelan L(2,1) pada Graf Sierpinski S(n,k). Karismatika, 3(2), 130-139.

Shao, Z., Yeh, R. K., & Zhang, D. (2008). The L (2, 1)-labeling on graphs and the frequency assignment problem. Applied Mathematics Letters, 21(1), 37-41. https://doi.org/10.1016/j.aml.2006.08.029

Umam, I. A. I., Halikin, I., & Fatekurohman, M. (2022, February). L (2, 1) Labeling of Lollipop and Pendulum Graphs. In International Conference on Mathematics, Geometry, Statistics, and Computation (IC-MaGeStiC 2021) (pp. 44-47). Atlantis Press. https://doi.org/10.2991/acsr.k.220202.010

Vinutha, M. S., & Arathi, P. (2017). Applications of graph coloring and labeling in computer science. International Journal on Future Revolution in Computer Science and Communication Engineering, 3(8), 14-16.

Wijaya, K., & Baskoro, E. T. (2016). On Ramsey (2K_2, 2H)(2 K 2, 2 H)-Minimal Graphs. In Applied Analysis in Biological and Physical Sciences: ICMBAA, Aligarh, India, June 2015 (pp. 219-225). Springer India.

Wallis, W. D. (2001). Magic Graphs. Birkhauser. Boston.

Published

2025-06-26