Pelabelan Jumlah Ganjil-Genap pada Beberapa Graf Pohon

Authors

  • Hafif Komarullah Tadris Matematika, Universitas Al-Falah As-Sunniyah, Kencong-Jember
  • Maura Delva Saputri Tadris Matematika, Universitas Al-Falah Assunniyah
  • Dwi Margi Utami

Keywords:

Pelabelan graf, pelabelan jumlah ganjil-genap, graf pohon

Abstract

Teori graf merupakan salah satu topik matematika yang terus berkembang hingga saat ini, salah satu topik yang dikembangkan adalah pelabalen graf. Pelabelan graf memiliki banyak terapan dalam kehidupan sehari-hari, seperti penentuan frekuensi radio, kriptografi, kristalografi, jaringan komunikasi, dan komputer sains. Hingga saat ini pelabelan graf terdiri dari berbagai jenis seperti pelabelan L(2,1), pelabelan prima, dan pelabelan jumlah ganjil-genap. graf G(V,E) dengan order p dan ukuran q dikatakan graf jumlah ganjil-genap jika terdapat fungsi injektif f:V(G)→{±1,±3,…±(2p-1)} sedemikian sehingga fungsi sisi terinduksi f^*:E(G)→{2,4,…,2q} yang didefinisikan oleh fungsi f^* (uv)=f(u)+f(v),∀uv∈E(G) merupakan fungsi bijektif. Dalam penelitian ini, peneliti menunjukkan bahwa graf sapu, graf sisir, graf hasil identifikasi titik dua graf bintang homogen, dan graf hasil identifikasi titik graf sapu dan graf lintasan merupakan graf jumlah ganjil-genap. Identifikasi titik dari graf G dan H pada titik x∈V(G) dan y∈V(H) dinotasikan dengan (G⨀_xy▒H) menghasilkan graf baru yang didapat dengan menempelkan titik x dan y sedemikian sehingga graf baru tersebut memiliki (|V(G)|+|V(H)|-1) titik dan (|E(G)|+|E(H)|) sisi. Dalam menunjukkan graf sapu, graf sisir, graf hasil identifikasi titik dua graf bintang homogen, dan graf hasil identifikasi titik graf sapu dan graf lintasan merupakan graf jumlah ganjil-genap, peneliti menggunakan metode studi pustaka, metode deskriptif aksiomatik, dan metode pendeteksian pola.

References

Berliner, A.H., N. Dean., J. Hook., A. Marr., A. Mbirika, dan C.D. McBee. 2016. Coprime and Prime Labellings of Graphs. Journal of Integer Sequence. 19(2): 1-14. https://doi.org/10.48550/arXiv.1604.07698

Borowiecka-Olszewska, M., & Hałuszczak, M. (2013). On Ramsey (K1, m, G)-minimal graphs. Discrete Mathematics, 313(19), 1843-1855. https://doi.org/10.1016/j.disc.2012.06.020

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

Dhanalakshmi, S., & Parvathi, N. (2018, April). Mean square cordial labelling related to some acyclic graphs and its rough approximations. In Journal of physics: Conference series (Vol. 1000, No. 1, p. 012040). IOP Publishing. https://doi.org/10.1088/1742-6596/1000/1/012040

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

Ghosh, P., & Pal, A. (2015). Some results of labeling on broom graph. Journal: JOURNAL OF ADVANCES IN MATHEMATICS, 9(9), 3055-3061. https://core.ac.uk/download/pdf/322470979.pdf

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

Hartsfield, N., & Ringel, G. (2013). Pearls in graph theory: a comprehensive introduction. Courier Corporation.

Janani, R. dan T. Ramachandran. 2023. Coprime Edge Labeling of Graphs. SSRN. 1-11. http://dx.doi.org/10.2139/ssrn.4486269

Janani, R., & Ramachandran, T. (2022). On Relatively Prime Edge Labeling of Graphs. Engineering Letters. 30(2): 659-665.

https://www.engineeringletters.com/issues_v30/issue_2/EL_30_2_30.pdf

Kaneria, V. J., Teraiya, O., & Bhatt, P. (2018). Generalized odd-even sum labeling and some α-odd-even sum graphs. International journal of Mathematics and its Applications, 6(1-B), 381-385.

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

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

Latifi, S. (2007). A study of fault tolerance in star graph. Information Processing Letters, 102(5), 196-200. https://doi.org/10.1016/j.ipl.2006.12.013

Manolopoulos, Y. (2024). Thematic Editorial: The Ubiquitous Network. The Computer Journal, 67(3), 809-811. https://doi.org/10.1093/comjnl/bxae032

Marr, A., & Denis, W.W. (2013). Magic Graphs, Birkhauser. Boston.

Monika, K., & Murugan, K. (2017). Odd-even sum labeling of some graphs. International Journal of Mathematics and Soft Computing, 7(1), 57-63. https://dx.doi.org/10.26708/ijmsc.2017.1.7.07.

Monika, K., & Murugan, K. (2018). Odd-even sum labeling in the context of duplication of graph elements. Mapana Journal of Sciences, 17(3), 17. https://doi.org/10.12723/mjs.46.2

Monika, K., & Murugan, K. (2021). Odd-even sum labeling of some disconnected graphs. Advances & Applications in Discrete Mathematics, 28(1). https://doi.org/10.17654/DM028010001

Monika, K., Murugan, K., & Balaji, V. (2022, January). A method of AMGL coding technique on odd-even sum labeling. In American Institute of Physics Conference Series (Vol. 2385, No. 1, p. 130036). https://doi.org/10.1063/5.0070863

Nurhakim, R., & Harianto, B. (2020). An odd-even sum labeling of jellyfish and mushroom graphs. InPrime: Indonesian Journal of Pure and Applied Mathematics, 2(2), 87-90. https://doi.org/10.15408/inprime.v2i2.14620

Pavlopoulos, G. A., Secrier, M., Moschopoulos, C. N., Soldatos, T. G., Kossida, S., Aerts, J., & Bagos, P. G. (2011). Using graph theory to analyze biological networks. BioData mining, 4, 1-27. https://link.springer.com/article/10.1186/1756-0381-4-10

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

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.

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

Published

2025-06-26