J. D IFERENSIAL / E -ISSN:2775-9644
Vol.5(1),2023, 22–28
doi: https://doi.org/10.35508/jd.v5i1.9824

## A RTIKEL P ENELITIAN
Pelabelan Harmonis Ganjil Pada Graf C m,n ⊵ e C 4
Demetriana Kolo 1,* , Keristina Br Ginting 1 , Ganesha L. Putra 1
1 Program Studi Matematika, Universitas Nusa Cendana,Kupang-NTT, Indonesia
* Penulis korespondensi: demetrianakolo053@gmail.com
Diterima: 25 Februari 2023; Direvisi: 12 Maret 2023; Disetujui: 13 Maret 2023; Dipublikasi:15 Maret 2023.
Abstrak :
Graf merupakan suatu pasangan terurut dari himpunan titik dan himpunan sisi yang memiliki keterkaitan dengan berbagai teori salah satunya pelabelan. Pelabelan suatu graf dapat dilakukan dengan banyak cara, salah satunya adalah pelabelan harmonis ganjil. Pelabelan harmonis ganjil merupakan suatu fungsi injektif f : V ( G ) → { 0 , 1 , 2 , . . . , 2 q − 1 } sehingga menginduksi fungsi bijektif f ∗ : E ( G ) → { 1 , 3 , 5 , . . . , 2 q − 1 } yang didefinisikan oleh f ∗ ( uv ) = f ( u ) + f ( v ) . Penelitian ini bertujuan untuk mengkontruksi pelabelan harmonis ganjil pada graf C m,n ⊵ e C 4 . Hasil yang diperoleh menunjukkan bahwa graf C m,n ⊵ e C 4 merupakan graf harmonis ganjil.
Kata Kunci: Teori Graf, Pelabelan Harmonis Ganjil, Graf C m,n ⊵ e C 4
Abstract : Graph is an ordered pair of a vertex and edge set that related with various theories, one of them called labeling. There are a lot of types of graph labeling, one of them is odd harmonious labeling. The odd harmonious labeling is an injective function f : V ( G ) → { 0 , 1 , 2 , . . . , 2 q − 1 } such that induced a bijective function is f ∗ : E ( G ) → { 1 , 3 , 5 , · · · , 2 q − 1 } which is defined by f ∗ ( uv ) = f ( u ) + f ( v ) . This study aims to construct an odd harmonious labeling on a graph C m,n ⊵ e C 4 . The results showed that a graph C m,n ⊵ e C 4 is an odd harmonious graph.
Keywords: Graph theory, odd harmonious labeling, C m,n ⊵ e C 4 graph

## 1. Pendahuluan
Teori graf pertama kali dikenalkan oleh Leonhard Euler, seorang matematikawan asal Swiss pada tahun 1736. Ide ini ditemukan saat ia hendak memecahkan masalah jembatan Konisberg, sehingga kisah jembatan Konigsberg ini menjadi sejarah lahirnya teori graf. Secara umum, graf G merupakan suatu pasangan terurut G = ( V, E ) dengan V suatu himpunan tak kosong yang beranggotakan titik dan E himpunan sisi dengan anggotanya merupakan himpunan bagian dari V yang berkardinalitas dua [1] . Ada pun aplikasi pada graf yang digunakan dalam kehidupan sehari-hari, contohnya Aplikasi teori graf di media sosial dalam menghubungkan teman. Pengguna di situs jejaring sosial seperti facebook , whatsapp , messenger , twitter , dan google .
Selain itu, penerapan graf lainnya yang dikenal adalah pelabelan graf. Pelabelan graf merupakan salah satu topik dari teori graf yang mendapat perhatian khusus, karena model-model yang ada pada teori graf berguna untuk aplikasi yang luas.Pelabelan pada graf adalah suatu pemetaan himpunan
© Kolo, dkk.
elemen-elemen pada graf ke suatu himpunan bilangan bulat yang dinamakan label [2] . Terdapat berbagai pelabelan graf, salah satunya pelabelan harmonis.
Pelabelan harmonis pertama kali diperkenalkan pada tahun 1980 oleh Graham dan Sloane [3] . Pelabelan harmonis merupakan jenis pelabelan titik. Pelabelan harmonis dibagi menjadi dua yaitu pelabelan harmonis ganjil dan pelabelan harmonis genap. Dalam penelitian ini penulis membahas tentang pelabelan harmonis ganjil yang dikenalkan oleh Liang dan Bai pada tahun 2009 [4] . Pelabelan harmonis dikatakan ganjil karena jumlah setiap label-label titik yang bertetangga membentuk barisan bilangan ganjil yang dimulai dari satu sampai dengan 2 q − 1 dengan q menyatakan banyaknya sisi [5] .
Adapun hasil-hasil penelitian tentang pelabelan harmonis ganjil sebagai berikut. Alyani dkk. telah menyelidiki pelabelan harmonis ganjil pada graf kC 4 dan graf kC 8 [6] . Sabrina Shena Sarasvati dkk. memberikan hasil terkait pelabelan harmonis ganjil pada graf P n ⊵ e C 4 dan P n ⊵ e D 2 ( C 4 ) [7] . Abdel-Aal telah menggeneralisasikan hasil dengan menunjukkan bahwa graf kC n untuk n = 0 (mod 4) adalah harmonis ganjil [8] . Dian Ayu Pujiwati juga memberikan hasil terkait pelabelan harmonis ganjil pada graf bintang ganda S n,m dan graf C m ⊙ K 1 ,n [9] . Jeyanthi dkk. membuktikan bahwa graf pohon pisang dan gabungan lintasan dari siklus C n untuk n = 0( mod 4) merupakan grafharmonis ganjil [10] . Fery Firmansah membuktikan eksistensi pelabelan harmonis ganjil pada graf ular dan graf ular berlipat [11] . Zulfi Amri dkk. juga membuktikan pelabelan harmonis ganjil pada graf 2 S n ( C 4 , n ) [12] .

## 2. Hasil Utama
Misalkan graf C m,n ⊵ e C 4 dengan himpunan titik yaitu V = { u i | i ∈ [1 , m ] ∪ { v i j, 1 , v i j, 2 , v i j, 3 | i ∈ [1 , m ] , j ∈ [1 , n ] } ∪ { u k, 1 , u k, 2 | k ∈ [1 , m − 1] } dan himpunan sisi yang diketahui dalam pelabelan ini adalah E = { u k u k, 1 , u k, 2 u k +1 , u k u k +1 , u k, 1 u k, 2 }| k ∈ [1 , m − 1] } ∪ { u i v i j, 1 , v i j, 1 v i j, 2 , v i j, 2 v i j, 3 , v i j, 3 u i | i ∈ [1 , m ] , j ∈ [1 , n ] } dengan | V ( C m,n ⊵ e C 4 ) | = 3 mn + 3 m − 2 dan | E ( C m,n ⊵ e C 4 ) | = 4 mn + 4 m − 4 . Berikut diberikan Lema yang digunakan dalam membuktikan pelabelan harmonis ganjil pada graf C m,n ⊵ e C 4 .
Lema 2.1. Misalkan g : A → B fungsi dan | A | = m, | B | = n berhingga, m, n ∈ N, m ≤ n , jika | A | = | R ( g ) | , maka g fungsi injektif.
Bukti . Ambil sembarang u i , u j ∈ A dengan i ̸ = j , i ∈ [1 , m ] , j ∈ [1 , m ] . Menurut premis, | A | = | R ( g ) | . Hal ini berarti bahwa g ( u 1 ) ̸ = g ( u 2 ) ̸ = g ( u 3 ) ̸ = . . . ̸ = g ( u n ) . Akibatnya, untuk i ̸ = j , g ( u i ) ̸ = g ( u j ) . Jadi, g fungsi injektif.
Lema 2.2. Misalkan g : A → B fungsi dan | A | = m, | B | = n berhingga, m, n ∈ N, m ≤ n , jika | R ( g ) | = | A | dan | R ( g ) | = | B | , maka g fungsi bijektif
Bukti . Suatu fungsi dikatakan bijektif apabila fungsi tersebut memenuhi sifat injektif dan sifat surjektif. Oleh karena itu ditunjukan fungsi injektif dan fungsi surjektif untuk membuktikan Lema 2.2 sebagai berikut. Diketahui g : A → B suatu fungsi. Misalkan A = { u 1 , u 2 , · · · , u m } , maka R ( g ) = { g ( u 1 ) , g ( u 2 ) , · · · , g ( u m ) } berhingga, m, n ∈ N . Ambil sembarang u i , u j ∈ A dengan i ̸ = j , i ∈ [1 , m ] , j ∈ [1 , m ] . Menurut premis, | A | = | R ( g ) | . Hal ini berarti bahwa g ( u 1 ) ̸ = g ( u 2 ) ̸ = g ( u 3 ) ̸ = . . . ̸ = g ( u n ) . Akibatnya, untuk i ̸ = j , g ( u i ) ̸ = g ( u j ) . Jadi, g fungsi injektif. Kemudian, menurut premis diperoleh R ( g ) = B . Perhatikan bahwa | R ( g ) | = m, | B | = n . Akibatnya, m = n . Ambil sebarang v ∈ B . Berdasarkan premis, v ∈ R ( g ) sehingga terdapat u ∈ A dan g ( u ) = v . Jadi, g surjektif. Dengan demikian, terbukti bahwa g fungsi bijektif karena telah memenuhi sifat-sifat fungsi injektif dan sifat surjektif.
Selanjutnya dibuktikan bahwa graf C m,n ⊵ e C 4 merupakan graf harmonis ganjil.
Teorema 2.1. Graf C m,n ⊵ e C 4 merupakan graf harmonis ganjil dengan m ∈ N, m ≥ 2 .
Bukti . Berdasarkan himpunan titik dan himpunan sisi dari graf C m,n ⊵ e C 4 diperoleh p = | V ( C m,n ⊵ e C 4 ) | = 3 mn +3 m − 2 dan q = | E ( C m,n ⊵ e C 4 ) | = 4 mn +4 m − 4 . Kemudian, definisikan fungsi pelabelan titik pada graf C m,n ⊵ e C 4 , yakni f : V ( C m,n ⊵ e C 4 ) → { 0 , 1 , 2 , · · · , 8 m ( n + 1) − 9 } sebagai berikut.
f ( u i ) = ( 2( n + 1)( i − 1) i ganjil , i ∈ [1 , m ]
2( n + 1) i − 1 i genap , i ∈ [1 , m ] f ( v i j, 1 ) = ( (2 n + 2)( i − 1) + 4 j − 3 i ganjil , i ∈ [1 , m ] , j ∈ [1 , n ] (2 n + 2)( i − 2) + 4 j − 2 i genap , i ∈ [1 , m ] , j ∈ [1 , n ]
f ( v i j, 2 ) = ( 8 m ( n + 1) − 4 − 8 j − 6( n + 1)( i − 1) i ganjil , i ∈ [1 , m ] , j ∈ [1 , n ] 8 m ( n + 1) − 4 − 8 j − 4 n − 5 − 6( n + 1)( i − 1) i genap , i ∈ [1 , m ] , j ∈ [1 , n ] f ( v i j, 3 ) = ( (2 n + 2)( i − 1) + 4 j − 1 i ganjil , i ∈ [1 , m ] , j ∈ [1 , n ] (2 n + 2)( i − 2) + 4 j i genap , i ∈ [1 , m ] , j ∈ [1 , n ]
f ( u k, 1 ) = ( 2( n + 1)( k + 1) − 3 k ganjil , k ∈ [1 , m − 1] 2( n + 1)( k ) − 2 k genap , k ∈ [1 , m − 1]
f ( u k, 2 ) = ( 8 m ( n + 1) − 12 − 8 n − 6( n + 1)( k − 1) k ganjil , k ∈ [1 , m − 1] 8 m ( n + 1) − 17 − 12 n − 6( n + 1)( k − 2) k genap , k ∈ [1 , m − 1]
Berdasarkan definisi fungsi pelabelan titik di atas, berikut dibuktikan bahwa f fungsi injektif. Untuk membuktikan f fungsi injektif cukup dibuktikan bahwa | D ( f ) | = | R ( f ) | menurut Lema 2.1 , dengan | D ( f ) | = | R ( f ) | = 3 mn + 3 m − 2 . Berikut diberikan himpunan daerah hasil dari fungsi f . Misalkan R 1 , R 2 , R 3 , . . . R 12 secara berturut-turut merupakan himpunan daerah hasil dari (1) . u i untuk i ganjil; (2) . u i untuk i genap; (3) . v i j, 1 untuk i ganjil; (4) . v i j, 1 untuk i genap; (5) . v i j, 2 untuk i ganjil; (6) . v i j, 2 untuk i genap; (7) . v i j, 3 untuk i ganjil; (8) . v i j, 3 untuk i genap; (9) . u k, 1 untuk k ganjil; (10) . u k, 1 untuk k genap; (11) . u k, 2 untuk k ganjil; (12) . u k, 2 untuk k genap.
Perhatikan bahwa dengan metode yang rutin dapat ditunjukkan R i ∩ R j = ∅ untuk i ̸ = j, i ∈ [1 , 12] , j ∈ [1 , 12] . Kemudian, dihitung kardinalitas R ( f ) untuk menunjukkan bahwa | R ( f ) | = | D ( f ) | . Oleh karena R i ∩ R j = ∅ untuk i ̸ = j , i ∈ [1 , 12] , j ∈ [1 , 12] , diperoleh
| R ( f ) | = | 12 [ a =1 R a | | R ( f ) | = 12 X a =1 | R a | − X 1 ≤ a<b ≤ 12 | R a ∩ R b | + X 1 ≤ a<b<c ≤ 12 | R a ∩ R b ∩ R c |− X 1 ≤ a<b<c<d ≤ 12 | R a ∩ R b ∩ R c ∩ R d | + X 1 ≤ a<b<c<d<e ≤ 12 | R a ∩ R b ∩ R c ∩ R d ∩ R e |− X 1 ≤ a<b<c<d<e<f ≤ 12 | R a ∩ R b ∩ R c ∩ R d ∩ R e ∩ R f | + X 1 ≤ a<b<c<d<e<f <g ≤ 12 | R a ∩ R b ∩ R c ∩ R d ∩ R e ∩ R f ∩ R g |− X 1 ≤ a<b<c<d<e<f <g<h ≤ 12 | R a ∩ R b ∩ R c ∩ R d ∩ R e ∩ R f ∩ R g ∩ R h | + X 1 ≤ a<b<c<d<e<f <g<h<i ≤ 12 | R a ∩ R b ∩ R c ∩ R d ∩ R e ∩ R f ∩ R g ∩ R h ∩ R i |− X
1 ≤ a<b<c<d<e<f <g<h<i<j ≤ 12 | R a ∩ R b ∩ R c ∩ R d ∩ R e ∩ R f ∩ R g ∩ R h ∩ R i ∩ R j | + X 1 ≤ a<b<c<d<e<f <g<h<i<j<k ≤ 12 | R a ∩ R b ∩ R c ∩ R d ∩ R e ∩ R f ∩ R g ∩ R h ∩ R i ∩ R j ∩ R k |− | R 1 ∩ R 2 ∩ R 3 ∩ R 4 ∩ R 5 ∩ R 6 ∩ R 7 ∩ R 8 ∩ R 9 ∩ R 10 ∩ R 11 ∩ R 12 | = 12 X a =1 | R a | − 0 + 0 − 0 + 0 − 0 + 0 − 0 + 0 − 0 + 0 − 0 = ( | R 1 | + | R 2 | ) + ( | R 3 | + | R 4 | ) + ( | R 5 | + | R 6 | ) + ( | R 7 | + | R 8 | ) + ( | R 9 | + | R 10 | ) + ( | R 11 | + | R 12 | ) = m + mn + mn + mn + m − 1 + m − 1
= m + 3 mn + 2 m − 2 = 3 mn + 3 m − 2
Perhatikan bahwa dari perhitungan kardinalitas R ( f ) di atas, diperoleh | R ( f ) | = 3 mn + 3 m − 2 . Oleh karena | D ( f ) | = | R ( f ) | , dimana | D ( f ) | = | V ( C m,n ⊵ e C 4 ) | = 3 mn + 3 m − 2 , maka berdasarkan Lema 2.1 , terbukti bahwa f fungsi injektif. Selanjutnya, definisikan fungsi f ∗ yang merupakan fungsi induksi dari fungsi f , yakni f ∗ : E ( C m,n ⊵ e C 4 ) → { 1 , 3 , 5 , · · · , 8 m ( n + 1) − 9 } sebagai berikut.
f ∗ ( u k u k +1 ) = f ( u k ) + f ( u k +1 ) =4( n + 1) k − 1 f ∗ ( u k u k, 1 ) = f ( u k ) + f ( u k, 1 ) = 4( n + 1)( k ) − 3 f ∗ ( u k, 2 u k +1 ) = f ( u k, 2 ) + f ( u k +1 ) = 8 m ( n + 1) − 4( n + 1) k − 5 f ∗ ( u k, 1 u k, 2 ) = f ( u k, 1 ) + f ( u k, 2 ) = 8 m ( n + 1) − 4( n + 1) k − 7 f ∗ ( u i v i j, 1 ) = f ( u i ) + f ( v i j, 1 ) = 4( n + 1)( i − 1) + 4 j − 3 f ∗ ( u i v i j, 3 ) = f ( u i ) + f ( v i j, 3 ) = 4( n + 1)( i − 1) + 4 j − 1 f ∗ ( v i j, 1 v i j, 2 ) = f ( v i j, 1 ) + f ( v i j, 2 ) = 8 m ( n + 1) − 4( n + 1)( i − 1) − 4 j − 7 f ∗ ( v i j, 2 v i j, 3 ) = f ( v i j, 2 ) + f ( v i j, 3 ) = 8 m ( n + 1) − 4( n + 1)( i − 1) − 4 j − 5
Berdasarkan definisi fungsi sisi di atas, berikut dibuktikan bahwa f ∗ fungsi bijektif dengan menggunakan Lema 2.2 , yakni membuktikan bahwa | D ( f ∗ ) | = | R ( f ∗ ) | = 4 mn + 4 m − 4 dan | R ( f ∗ ) | = |{ 1 , 3 , 5 , · · · , 8 m ( n + 1) − 9 }| = 4 mn + 4 m − 4 . Misalkan D 1 , D 2 , D 3 , . . . , D 8 secara berturut- turut merupakan himpunan daerah hasil dari (1) . u k u k +1 ; (2) . u k u k, 1 ; (3) . u k, 2 u k +1 ; (4 . ) u k, 1 u k, 2 ; (5) . u i v i j, 1 ; (6) . u i v i j, 3 ; (7) . v i j, 1 v i j, 2 ; (8) . v i j, 2 v i j, 3 . Perhatikan bahwa dengan metode perbandingan antar anggota himpunan, diperoleh D i ∩ D j = ∅ untuk i ̸ = j, i ∈ [1 , 8] dan j ∈ [1 , 8] . Kemudian, dihitung kardinalitas R ( f ∗ ) untuk menunjukkan bahwa | R ( f ∗ ) | = | D ( f ∗ ) | .
| R ( f ∗ ) | = | 8 [ s =1 D s | | R ( f ∗ ) | = 8 X s =1 | D s | − X 1 ≤ s<t ≤ 12 | D s ∩ D t | + X 1 ≤ s<t<u ≤ 8 D s ∩ D t ∩ D u − X 1 ≤ s<t<u<v ≤ 8 | D s ∩ D t ∩ D u ∩ D v | + X 1 ≤ s<t<u<v<w ≤ 8 | D s ∩ D s ∩ D t ∩ D u ∩ D v |− X 1 ≤ s<t<u<v<w<x ≤ 8 | D s ∩ D t ∩ D u ∩ D v ∩ D w ∩ D x | + X 1 ≤ s<t<u<v<w<x<y ≤ 8 | D s ∩ D t ∩ D u ∩ D v ∩ D w ∩ D x ∩ D y | − | D 1 ∩ D 2 ∩ D 3 ∩ D 4 ∩ D 5 ∩ D 6 ∩ D 7 ∩ D 8 | = 8 X s =1 | D s | − 0 + 0 − 0 + 0 − 0 + 0 − 0 = ( | D 1 | + | D 2 | ) + ( | D 3 | + | D 4 | ) + ( | D 5 | + | D 6 | ) + ( | D 7 | + | D 8 | ) = m − 1 + m − 1 + m − 1 + m − 1 + mn + mn + mn + mn = 4 m − 4 + 4 mn = 4 mn + 4 m − 4
Berdasarkan perhitungan kardinalitas R ( f ∗ ) di atas, diperoleh | R ( f ∗ ) | = 4 mn + 4 m − 4 . Oleh karena | D ( f ∗ ) | = | R ( f ∗ ) | dan |{ 1 , 3 , 5 , · · · , 8 m ( n + 1) − 9 }| = 4 mn + 4 m − 4 maka | R ( f ∗ ) | = |{ 1 , 3 , 5 , · · · , 8 m ( n + 1) − 9 }| . Akibatnya, berdasarkan Lema 2.2 , terbukti bahwa f ∗ fungsi bijektif. Jadi berdasarkan pembuktian di atas, diperoleh graf C m,n ⊵ e C 4 merupakan graf harmonis ganjil. Berikut diberikan contoh pelabelan harmonis ganjil pada graf C 4 , 3 ⊵ e C 4 .
Gambar 2.1: Pelabelan Harmonis Ganjil pada Graf C 4 , 3 ⊵ e C 4

## 3. Kesimpulan dan Saran

## 3.1. Kesimpulan
Berdasarkan hasil dan pembahasan di atas, diperoleh kesimpulan bahwa graf C m,n ⊵ e C 4 , merupakan graf harmonis ganjil untuk m ≥ 2 , m ∈ N dan n ≥ 1 , n ∈ N .

## 3.2. Saran
Kajian ini dapat dilanjutkan dengan melakukan penelitian pada graf C m,n ⊵ e C q , m ∈ N , n ≥ 2 , n ∈ N , dan q genap, q > 4 , q ∈ N .

## Referensi
[1] C. Gary and P. Zhang, “A first course in graph theory,” McGraw Hill , 2012. View online .
[2] J. A. Gallian, “A dynamic survey of graph labeling,” Electronic Journal of combinatorics , vol. 1, 2018. View online .
[3] R. L. Graham and N. J. A. Sloane, “On additive bases and harmonious graphs,” SIAM Journal on Algebraic Discrete Methods , vol. 1, no. 4, pp. 382–404, 1980. View online .
[4] Z. Liang and L. Z, On odd harmonious graphs with applications , vol. 29. J. Appl. Math. Comput., 2009. View online .
[5] F. Fery and M. W. Syaifuddin, “Pelabelan harmonis ganjil pada amalgamasi graf kincir angin belanda,” Fibonacci , vol. 4, no. 1, 2018. View online .
[6] W. G. F. Alyani, F. Firmansah and K. A. Sugeng, pelabelan harmonis ganjil pada graf kC 4 ular untuk spesifik nilai dari n, yaitu untuk n=4 dan n=8 . Proceeding of IICMA, 2013. View online . [7] S. S. Sarasvati, I. Halikin, and K. Wijaya, “On odd harmonious labeling of p n ⊵ c 4 and p n ⊵ d 2 ( c 4 ) ,” Indonesia Journal of Combinatorics , 2021. View online .
[8] M. Abdel-Aal, “New families of odd harmonious graphs,” Internat. J. Soft Comput., Math. Control , vol. 3, no. 1, pp. 1–13, 2004. View online .
[9] D. A. Pujiwati, Pelabelan Harmonis Ganjil pada Graf Bintang Ganda ( S n , m ) dan Graf C m J K 1 , n . Skripsi, Universitas Jember, 2020. View online .
[10] P. Jeyanthi and S. Philo, “Odd harmonious labeling of some new families of graphs,” Electronic Notes in Discrete Mathematics , vol. 48, pp. 165–168, 2015. View online .
[11] F. Firmansah, “Pelabelan harmonis ganjil pada graf ular jaring berlipat,” Sainmatika: Jurnal Matematika dan Ilmu Pengetahuan Alam , vol. 17, no. 1, 2020. View online .
[12] Z. Amri, A. Aulia, A. Syella, H. Pratama, S. Ramadhan, and Chairunnisa, “Pelabelan harmonis ganjil pada graf 2 s n ( c 4 ,n ),” Edutech: Jurnal Ilmu Pendidikan dan Ilmu Sosial , vol. 4, 2018. View online .
Format Sitasi IEEE :
D. Kolo, K. Ginting, G.L. Putra, “Pelabelan Harmonis Ganjil Pada Graf C m,n ⊵ e C 4 ”, Jurnal Diferensial , vol. 5(1), pp. 22-28,2023.
This work is licensed under a Creative Commons “Attribution- ShareAlike 4.0 International” license.