Syntax Literate: Jurnal Ilmiah Indonesia p–ISSN: 2541-0849 e-ISSN: 2548-1398

Vol. 9, No. 7, Juli 2024

INDEKS WIENER DARI GRAF IDENTITAS DAN GRAF PANGKAT PADA GRUP SIKLIS BERHINGGA

Darmajid^1*, Noor Hidayat², Wildan Bagus Wicaksono³, Ayunda Faizatul Musyarrofah⁴

Universitas Brawijaya, Malang, Indonesia^1,2,3,4

Email: [email protected]^1*

Abstrak

Graf identitas atas suatu grup didefinisikan sebagai graf dengan himpunan titiknya berupa unsur-unsur grup dan dua titik dihubungkan oleh sebuah sisi jika hasil kalinya merupakan unsur identitas atau tepat salah satu dari kedua titik merupakan unsur identitas pada grup. Graf pangkat atas suatu grup didefinisikan sebagai graf dengan himpunan titiknya berupa unsur-unsur grup dan dua titik dihubungkan oleh sebuah sisi jika satu titik dapat dituliskan sebagai perpangkatan dari titik lainnya. Pada penelitian ini dikaji formulasi indeks Wiener dari graf identitas dan graf pangkat pada grup siklik berhingga. Hasil formulasi indeks Wiener dari graf identitas terbagi atas grup siklis orde 1, orde ganjil lebih dari 1 dan orde genap sedangkan dari graf pangkat difokuskan pada grup siklis berode perpangkatan bilangan prima dan perkalian dua prima berbeda.

Kata Kunci: Indeks Wiener, Graf identitas, Graf pangkat.

Abstract

An identity graph for a group is defined as a graph with a set of points consisting of group elements and two points connected by an edge if the product is an identity element or exactly one of the two points is an identity element in the group. A power graph of a group is defined as a graph with a set of points consisting of elements of the group and two points connected by an edge if one point can be written as a power of another point. In this research, we examine the formulation of the Wiener index for identity graphs and power graphs in finite cyclic groups. The results of the Wiener index formulation from identity graphs are divided into cyclical groups of order 1, odd order more than 1 and even order, while the power graph focuses on cyclic groups with the exponent of prime numbers and the product of two different primes.

Keywords: Wiener index, identity graph, power graph.

Pendahuluan

Teori graf merupakan cabang ilmu matematika yang pertama kali diperkenalkan oleh Leonhard Euler pada abad ke-18 (Biggs et al., 1986). Seiring berkembangnya ilmu pengetahuan, konstruksi graf tidak lagi terbatas pada analisis graf secara umum, tetapi juga dapat dibentuk dari struktur aljabar seperti grup. Salah satu jenis graf yang dibentuk dari struktur grup adalah graf identitas. Graf identitas pertama kali diperkenalkan pada tahun 2009 oleh Kandasamy dan Smarandache, yang didefinisikan sebagai graf dengan himpunan titiknya berupa elemen-elemen grup, di mana dua titik dihubungkan oleh sebuah sisi jika hasil kalinya merupakan unsur identitas atau tepat salah satunya merupakan unsur identitas (Kandasamy & Smarandache, 2009). Pada tahun 2020, Jeeshma melanjutkan penelitian terkait graf identitas dengan fokus pada pewarnaan titik dan sisi dari graf tersebut (Jeeshma, 2020). Pada tahun 2022, Alib dan Magpantay meneliti jarak, eksentrisitas, radius, diameter, dan center dari graf identitas pada grup siklik berhingga (Alib & Magpantay, 2022). Di sisi lain, terdapat graf pangkat yang juga dibentuk dari struktur grup. Graf ini pertama kali diperkenalkan oleh Chakrabarty dkk. pada tahun 2009, yang didefinisikan sebagai graf dengan himpunan titiknya berupa elemen-elemen semigrup, di mana dua titik dihubungkan oleh sebuah sisi jika satu titik dapat dituliskan sebagai perpangkatan dari titik lainnya (Chakrabarty et al., 2009). Selanjutnya, Cameron dan Ghosh melanjutkan penelitian mengenai graf pangkat pada grup berhingga (Cameron & Ghosh, 2011). Pada tahun 2017, Chattopadhyay dan Panigrahi memperkenalkan graf pangkat pada semigrup (Chattopadhyay & Panigrahi, 2017), dan kemudian pada tahun 2023, Swathi dan Sunitha mengembangkan konsep graf pangkat pada grup berhingga (Swathi & Sunitha, 2023).

Misalkan adalah graf sederhana dengan himpunan titik dan himpunan sisi Jarak dua titik dan pada graf didefinisikan sebagai panjang lintasan terpendek yang menghubungkan dan dan dinotasikan sebagai Jumlahan dari jarak di antara semua pasangan titik disebut sebagai indeks Wiener dan dinotasikan dengan Indeks Wiener adalah indeks topologi yang pertama kali diperkenalkan oleh seorang ahli kimia bernama Harold Wiener pada tahun 1947 untuk memprediksi titik didih dari struktur molekul parafin (Wiener, 1947). Indeks Wiener dapat merepresentasikan sifat fisikokimia suatu ikatan molekul karbon. Jika indeks Wiener semakin kecil, maka kekompakan molekulnya meningkat, sehingga titik didihnya menurun, dan berlaku sebaliknya (Hayat et al., 2018). Hasil penerapan Indeks Wiener dalam bidang kimia disajikan oleh Gutman pada tahun (1993) dan Nikolic pada tahun 1995 (1995).

Dalam bidang matematika, perhitungan indeks Wiener dari suatu graf mengalami perkembangan pesat seperti yang telah dilakukan oleh Polansky dan Bounchev pada tahun (1986). Beberapa peneliti juga merumuskan perhitungan indeks Wiener pada beberapa tipe graf khusus seperti graf pohon (Dobrynin et al., 2001; Entringer et al., 1976), graf nonbipartit (Chen et al., 2014), graf Euler (Gutman et al., 2014), serta graf bintang dan graf garis (Knor & Skrekovski, 2014). Selain itu, berkembang juga penelitian terkait indeks Wiener dari graf yang dibentuk dari struktur ring, seperti Ahmadi dan Jahani-Nezhad pada tahun 2011 meneliti indeks Wiener dari graf pembagi nol atas ring (Ahmadi & Jahani-Nezhad, 2011). Kemudian Singh dan Bath pada tahun 2021 meneliti indeks Wiener dari graf pembagi nol atas ring bilangan bulat modulo n (Singh & Bhat, 2021). Pada tahun 2022 Selvakumar dkk. meneliti indeks Wiener dari graf pembagi nol atas ring komutatif berhingga (Selvakumar et al., 2022). Melihat perkembangan penelitian dari indeks Wiener yang masih terbuka luas, secara spesifik belum dibahas indeks Wiener yang dibangun oleh struktur grup seperti graf identitas dan graf pangkat. Oleh karena itu, dalam paper ini akan dikaji indeks Wiener dari graf identitas dan graf pangkat pada grup siklik berhingga.

Kajian teori graf ini dibatasi hanya pada graf sederhana yang merupakan suatu graf tak berarah yang tidak mempunyai loop dan sisi ganda.

Grup Siklik (Gallian, 2021) Misalkan suatu grup dan Didefinisikan himpunan yang dibangun oleh sebagai

Grup disebut grup siklik jika terdapat sedemikian sehingga .

Teorema 2.2. (Gallian, 2021) Misalkan grup, dan . Jika memiliki order berhingga maka dan jika dan hanya jika membagi habis .

Misalkan adalah graf sederhana dengan himpunan titik dan himpunan sisi . Jarak dua titik di dan di , dinotasikan didefinisikan sebagai panjang lintasan terpendek yang menghubungkan dan . Jika titik dan berada pada komponen berbeda pada maka jaraknya tidak dapat ditentukan.

Graf Identitas (Gallian, 2021) Graf identitas dari grup adalah graf sederhana yang himpunan titiknya berupa elemen-elemen pada dan dua titik bertetangga jika dan hanya jika di mana elemen identitas pada

Graf Pangkat (Chakrabarty et al., 2009) Graf pangkat dari grup yang dinotasikan dengan adalah graf sederhana yang himpunan titiknya berupa elemen-elemen pada dan dua titik bertetangga jika dan hanya jika dan atau untuk suatu bilangan asli

Matriks Jarak (Chartrand et al., 2016) Misalkan suatu graf dengan himpunan titik Matriks jarak dari graf , dinotasikan (), merupakan matriks = dimana dan .

Indeks Wiener (Asir et al., 2022) Misalkan suatu graf dengan matriks jarak . Indeks Wiener dari , dinotasikan , didefinisikan sebagai

Metode Penelitian

Metode penelitian yang digunakan adalah studi literatur untuk menemukan formulasi indeks Wiener pada graf bentukan dari struktur aljabar grup siklik. Adapun langkah-langkah yang dilakukan dalam penelitian ini sebagai berikut.

1) Menghitung indeks Wiener dari graf identitas pada grup siklik berode 1, 2, 3 kemudian dikembangkan hingga orde .

2) Merumuskan indeks Wiener dari graf identitas pada grup siklik berode dan membuktikan kebenaran rumus tersebut.

3) Menghitung indeks Wiener dari graf pangkat pada grup siklik berode 1, 2, 3 kemudian dikembangkan hingga orde bilangan asli yang merupakan hasil perpangkatan bilangan prima maupun perkalian dua bilangan prima berbeda.

4) Merumuskan indeks Wiener dari graf identitas pada grup siklik berode dimana merupakan perpangkatan bilangan prima atau perkalian dua bilangan prima berbeda dan membuktikan kebenaran rumus tersebut.

Hasil dan Pembahasan

Berikut hasil yang diperoleh terkait formulasi Indeks Wiener dari Graf Identitas dan Graf Pangkat.

Teorema 3.1. Misalkan adalah grup siklis berorde dan adalah graf identitas atas . Indeks Wiener dari adalah

Bukti.

Jika maka sehingga merupakan matriks nol yang memaksa . Selanjutnya diasumsikan bahwa . Karena siklis maka terdapat sehingga . Tinjau kasus dimana Untuk setiap , terdapat tepat satu yang memenuhi yakni . Karena maka Ini berarti, hanya bertetangga dengan dan serta hanya bertetangga dengan dan . Hal ini menunjukkan bahwa sedangkan untuk setiap berlaku dan . Diperoleh,

Untuk , berlaku

Akibatnya, indeks Wiener dari graf identitas adalah

Selanjutnya, ditinjau kasus . Karena dan untuk setiap maka bertetangga dengan dan serta bertetangga dengan e dan . Lebih lanjut, hanya bertetangga dengan . Diperoleh,

dan

Untuk dengan berlaku

Akibatnya, indeks Wiener dari graf identitas adalah

Selanjutnya akan dihitung indeks Wiener dari graf pangkat atas grup siklis dengan orde tertentu. Misalkan siklis dengan orde . Ini berarti, terdapat sehingga . Jika maka jelas bahwa indeks Wiener dari graf pangkat atas grup adalah

Teorema 3.2. Misalkan adalah grup siklis berorde dan adalah graf pangkat atas . Jika untuk suatu bilangan prima dan bilangan asli maka Indeks Wiener dari adalah .

Bukti.

Misalkan . Perhatikan bahwa . Karena graf sederhana maka jika dan hanya jika bertetangga dengan setiap anggota lain di . Jika maka sehingga bertetangga dengan setiap anggota lain di . Ditinjau kasus . Perhatikan bahwa bertetangga dengan untuk setiap bilangan asli yang memenuhi . Bilangan asli yang memenuhi kondisi tersebut ada sebanyak . Karena maka haruslah bertetangga dengan setiap anggota pada yang memiliki sebanyaka anggota. Karena maka bertetangga dengan setiap anggota lain di . Akibatnya, disimpulkan bahwa setiap titik di saling bertetangga satu sama lain sehingga untuk setiap dan . Jadi, indeks Wiener dari graf pangkat adalah

Teorema 3.3. Misalkan adalah grup siklis berorde dan adalah graf pangkat atas . Jika dimana dan adalah dua bilangan prima berbeda maka Indeks Wiener dari adalah .

Bukti.

Misalkan . Untuk maka . Diasumsikan bahwa . Jika maka bertetangga dengan setiap anggota di sehingga berakibat Nilai yang demikian ada sebanyak sehingga didapat

Jika maka . Tinjau yang bertetangga dengan untuk setiap bilangan asli yang memenuhi , yakni sebanyak . Karena dan maka sehingga . Ini berarti, bertetangga dengan setiap anggota dari , yaitu sebanyak Karena maka tidak bertetangga dengan setiap anggota , yakni sebanyaka Diperoleh,

Banyaknya nilai yang memenuhi adalah sehingga

Secara analog, dengan kondisi dan akan didapat

Jadi, indeks Wiener dari graf pangkat adalah

Kesimpulan

Indeks Wiener dari graf identitas pada grup siklis berode adalah

Di pihak lain, Indeks Wiener dari graf pangkat pada grup siklis berode dan berode adalah masing-masing adalah

BIBLIOGRAFI

Ahmadi, M. R., & Jahani-Nezhad, R. (2011). Energy and Wiener index of zero-divisor graphs. Iranian Journal of Mathematical Chemistry, 2(1 (Special Issue on the Occasion of Mircea V. Diudea's Sixtieth Birthday)), 45–51.

Alib, C., & Magpantay, D. M. (2022). Some Parameters of the Central Graphs of the Identity Graphs of Finite Cyclic Groups. European Journal of Pure and Applied Mathematics, 15(3), 1098–1112.

Asir, T., Rabikka, V., Anto, A. M., & Shunmugapriya, N. (2022). Wiener index of graphs over rings: a survey. AKCE International Journal of Graphs and Combinatorics, 19(3), 316–324.

Biggs, N., Lloyd, E. K., & Wilson, R. J. (1986). Graph Theory, 1736-1936. Oxford University Press.

Cameron, P. J., & Ghosh, S. (2011). The power graph of a finite group. Discrete Mathematics, 311(13), 1220–1222.

Chakrabarty, I., Ghosh, S., & Sen, M. K. (2009). Undirected power graphs of semigroups. Semigroup Forum, 78, 410–426.

Chartrand, G., Lesniak, L., & Zhang, P. (2016). Graphs and Digraphs (Edisi ke-6). CRC press.

Chattopadhyay, S., & Panigrahi, P. (2017). Some structural properties of power graphs and k-power graphs of finite semigroups. Journal of Discrete Mathematical Sciences and Cryptography, 20(5), 1101–1119.

Chen, L., Li, X., & Liu, M. (2014). The (revised) Szeged index and the Wiener index of a nonbipartite graph. European Journal of Combinatorics, 36, 237–246.

Dobrynin, A. A., Entringer, R., & Gutman, I. (2001). Wiener index of trees: theory and applications. Acta Applicandae Mathematica, 66, 211–249.

Entringer, R. C., Jackson, D. E., & Snyder, D. A. (1976). Distance in graphs. Czechoslovak Mathematical Journal, 26(2), 283–296.

Gallian, J. (2021). Contemporary abstract algebra. Chapman and Hall/CRC.

Gutman, I. (1993). Chemical Graph Theory. Journal of Chemical Information and Modelling, 33, 79–85.

Gutman, I., Cruz, R., & Rada, J. (2014). Wiener index of Eulerian graphs. Discrete Applied Mathematics, 162, 247–250.

Hayat, S., Wang, S., & Liu, J.-B. (2018). Valency-based topological descriptors of chemical networks and their applications. Applied Mathematical Modelling, 60, 164–178.

Jeeshma, J. U. (2020). Coloring for the identity graphs of groups. International Research Journal of Engineering and Technology (IRJET), 7(5), 5965–5968.

Kandasamy, W. B., & Smarandache, F. (2009). Groups as graphs. ArXiv Preprint ArXiv:0906.5144.

Knor, M., & Skrekovski, R. (2014). Wiener index of generalized 4-stars and of their quadratic line graphs. Australas. J Comb., 58, 119–126.

Nicolic, S. (1995). Molecular Descriptors in Chemistry. Molecules, 27, 1–15.

Polansky, O. E., & Bonchev, D. (1986). The Wiener number of graphs. I. General theory and changes due to some graph operations. MATCH Commun. Math. Comput. Chem, 21(133–186), 72.

Selvakumar, K., Gangaeswari, P., & Arunkumar, G. (2022). The Wiener index of the zero-divisor graph of a finite commutative ring with unity. Discrete Applied Mathematics, 311, 72–84.

Singh, P., & Bhat, V. K. (2021). Adjacency matrix and Wiener index of zero divisor graph\varGamma (Z_n) Γ (Z n). Journal of Applied Mathematics and Computing, 66, 717–732.

Swathi, V., & Sunitha, M. S. (2023). k-Power Graphs of Finite Groups. ArXiv Preprint ArXiv:2301.10425.

Wiener, H. (1947). Structural determination of paraffin boiling points. Journal of the American Chemical Society, 69(1), 17–20.

Copyright holder:

Darmajid, Noor Hidayat, Wildan Bagus Wicaksono,

Ayunda Faizatul Musyarrofah (2024)

First publication right:

Syntax Literate: Jurnal Ilmiah Indonesia

This article is licensed under: