J. Math. and Its Appl. ISSN: 1829-605X Vol. 6, No. 1, May 2009, 25–33

## SUPER EDGE-MAGIC PADA GRAF YANG MEMUAT BEBERAPA CYCLE GANJIL

## Suhud Wahyudi, Chairul Imron
Jurusan Matematika, FMIPA ITS Surabaya suhud@matematika.its.ac.id, imron-its@matematika.its.ac.id

## Abstrak
Total edge-magic graph G adalah pemetaan bijektif f : V ∪ E → 1 , 2 , 3 , · · · , p + q sedemikian hingga f ( u ) + f ( e ) + f ( v ) adalah konstan tidak tergantung dari e = ( u, v ) ∈ E . Total edge-magic graph G dikatakan super edge-magic jika f ( V ( G )) = 1 , 2 , 3 , · · · , p . Dalam hal ini sifat super edge-magic dimiliki oleh beberapa graf yang memuat cycle ganjil. Salah satunya adalah graf planar ( P 2 ∪ kK 1 )+ N 2 dengan k > 1.
Dalam makalah ini dikembangkan suatu teorema baru ten- tang keberlakuan planar graph ( P 2 ∪ kK 1 ) + N 2 dari P 2 menjadi P 2 n , n = 1 , 2 , · · · . Juga ditunjukkan range dari kon- stanta magic total edge-magic labeling graph ( P 2 ∪ kK 1 )(+) N 2 . Katakunci: Total edge-magic, super edge-magic, consecutive.

## 1. Pendahuluan
graf adalah suatu cabang dari matematika yang pada akhir-akhir ini ber- kembang pesat. Salah satu bagian dari graf yang banyak diminati adalah graph labeling . graph labeling adalah pemberian nilai (integer positif) pada vertex, edge, atau vertex dan edge . Ada beberapa macam labeling , yaitu
26 Super Edge-Magic Pada Graf Yang Memuat Beberapa Cycle Ganjil
labeling yang domainnya berupa himpunan vertex , himpunan edge , atau keduanya, dan dinamakan dengan vertex labeling, edge labeling dan total labeling.
Penelitian labeling pertama kali dinamakan magic valuation yang dike- nalkan oleh A.Kotzig dan A.Rosa (1970) dan berkembang sampai sekarang dengan berbagai macam nama. Salah satu jenis graph labeling adalah ma- gic labeling yaitu vertex labeling dan edge labeling dari suatu graf dengan himpunan bilangan integer positif yang memenuhi sifat penjumlahannya adalah konstan.
Total edge-magic labeling dari ( p, q ) − graph G adalah fungsi bijek- tif f : V ( G ) ∪ E ( G ) → 1 , 2 , 3 , · · · , p + q sedemikian hingga untuk setiap xy ∈ E ( G ) dengan x, y ∈ V ( G ) berlaku f ( x ) + f ( xy ) + f ( y ) = k, k adalah suatu konstanta. Konstanta k disebut bilangan ajaib [7]. Jika G mempu- nyai sifat total edge-magic labeling , maka G disebut total edge-magic gra- ph. Super edge-magic labeling dari ( p, q ) − graph G adalah fungsi bijektif f : V ( G ) ∪ E ( G ) → 1 , 2 , 3 , · · · , p sedemikian hingga untuk setiap xy ∈ E ( G ) dengan x, y ∈ V ( G ) berlaku f ( x ) + f ( xy ) + f ( y ) = k, k adalah suatu kon- stanta, dan memenuhi sifat f ( V ( G )) = 1 , 2 , 3 , · · · , p . Konstanta k disebut bilangan ajaib [3]. Jika G mempunyai sifat super edge-magic labeling, maka G disebut super edge-magic graph.
Pengkajian mengenai total edge-magic graph dan super edge-magic gra- ph secara kontinu telah dilakukan. Misalnya Craft dan Tesar [2] serta Godbord dan Slater [6] menunjukkan bahwa semua cycle adalah total edge- magic. Sedangkan Enomoto dkk. [3] menunjukkan bahwa graph cycle ada- lah super edge-magic jika dan hanya jika n ganjil. Sin-Min Lee dan Alexan- der Nien-Tsu Lee [8] menunjukkan bahwa graf planar ( P 2 ∪ hK 1 )+ N 2 , h > 1, adalah super edge-magic.
Sebuah himpunan bagian S dari bilangan integer dikatakan consecutive jika S terdiri atas bilangan integer yang berurutan. Chen [1] menunjukkan bahwa sebuah graf G adalah super edge-magic jika dan hanya jika terda- pat suatu vertex labeling f sedemikian hingga dua himpunan f ( V ( G )) dan f ( u ) + f ( v ) : ( u, v ) ∈ E ( G ) keduanya adalah consecutive. Secara terpisah Figueroa-Centeno dkk. [5] juga memberikan hasil yang sama. Mereka me- nunjukkan bahwa jika f : V ( G ) → 1 , 2 , 3 , · · · , p adalah fungsi bijektif dari ( p, q ) − graph G dan S = f ( u ) + f ( v ) : uv ∈ E adalah consecutive dengan
s = min ( S ), maka f dapat diperluas menjadi super edge-magic labeling dari G didefinisikan oleh f ( uv ) = p + q + s − f ( u ) − f ( v ) untuk semua edge uv ∈ E ( G ). Jadi jelaslah bahwa untuk menunjukkan super edge-magic labeling graph cukup dengan vertex labeling yang menyebabkan concecuti- ve . Contoh dari concecutive labeling yang menyebabkan super edge-magic labeling dapat dilihat pada Gambar 1.
Consecutive labeling Super edge-magic labeling .
Gambar 1: Consecutive Labeling dan Super Edge-Magic Labeling
Suatu graf G dikatakan terhubung jika dapat dibuat lintasan yang menghubungkan setiap dua vertex pada graf tersebut. Graph terhubung yang membentuk cycle disebut graph cycle dilambangkan dengan C n , se- dangkan graf terhubung yang tidak mengandung cycle disebut graf pohon. Salah satu bentuk khusus dari graf pohon adalah graf lintasan dilambangk- an dengan P n . Graf yang setiap vertex nya terhubung dinamakan graf kom- plit dilambangkan dengan K n . Graf yang hanya terdiri dari simpul-simpul saja sebanyak m dinamakan graph Number dilambangkan dengan N m [9]

## 2. Graf yang Memuat Beberapa Cycle Ganjil
Suatu graf yang didalamnya memuat cycle ganjil dapat dibangun oleh bebe- rapa graf dengan operasi-operasi tertentu. Dalam hal ini operasi yang digu- nakan adalah ∪ , + atau (+). Untuk operasi ∪ dan + dapat dilihat pada [9],
28
Super Edge-Magic Pada Graf Yang Memuat Beberapa Cycle Ganjil
sedangkan untuk operasi (+) akan didefinisikan pada graf terkait. Misalkan P 2 n (+) N m adalah graf dengan p = 2 n + m dan q = 2( m + n ) − 1.
V ( P 2 n (+) N m ) = { v 1 , v 2 , · · · , v 2 n , y 1 , y 2 , . . . , y m } .
dengan
V ( P 2 n ) = { v 1 , v 2 , · · · , v 2 n }
dan
V ( N m ) = { y 1 , y 2 , · · · , y m } . E ( P 2 n (+) N m ) = E ( P 2 n ∪{ ( v 1 , y 1 ) , ( v 1 , y 2 ) , · · · , ( v 1 , y m ) } , { ( v 2 n , y 1 ) , ( v 2 n , y 2 )
· · · , ( v 2 n , y m ) } ) .
[5] menunjukkan bahwa P 2 (+) N m super edge-magic untuk semua m > 1. Dalam hal ini Sin-Min Lee dan Alexander Nien-Tsu Lee [8] mengembangk- an keberlakuan P 2 menjadi P 2 n seperti yang ditunjukkan dalam teorema berikut
Teorema 2.1 Graf P 2 n (+) N m adalah super edge-magic untuk semua n, m > 1 [8]
Graf planar ( P 2 ∪ hK 1 ) + N 2 adalah graf dengan p = h + 4 dan 2 h + 5.
V (( P 2 ∪ hK 1 ) + N 2 ) = { z 1 , z 2 , x 1 , x 2 · · · , x h , y 1 , y 2 }
dengan
V ( P 2 ) = { z 1 , z 2 } , V ( hK 1 ) = { x 1 , x 2 , · · · x h } , V ( N 2 ) = { y 1 , y 2 }
dan
E (( P 2 ∪ hK 1 ) + N 2 ) = { ( z 1 , z 2 ) , ( z 1 , y 1 ) , ( z 2 , y 1 ) , ( z 1 , y 2 ) , ( z 2 , y 2 ) , ( x 1 , y 1 ) , ( x 2 , y 1 ) , · · · , ( x h , y 1 ) , ( x 1 , y 2 ) , ( x 2 , y 2 ) , · · · , ( x h , y 2 ) } .
Graf planar ( P 2 ∪ hK 1 ) + N 2 ini memuat 2 C 3 dan hC 4 .
Teorema 2.2 Untuk h > 1 , graf planar P 2 ∪ hK 1 ) + N 2 adalah super edge- magic[8]
Gambar 2: Consecutive labeling yang menyebabkan Super edge-magic labe- ling dari P 2 ∪ hK 1 + N 2
Contoh 2.3 Consecutive labeling yang menyebabkan super edge-magic la- beling dari ( P 2 ∪ hK 1 ) + N 2 ditunjukkan pada Gambar 2
Graf ( P 2 n ∪ hK 1 )(+) N 2 , n = 1 , 2 , 3 , · · · adalah graph dengan p = 2 n + h + 2 dan q = 2 n + 2 h + 3. V (( P 2 n ∪ hK 1 )(+) N 2 ) = { z 1 , z 2 , · · · , z 2 n , x 1 , x 2 , · · · , x h , y 1 , y 2 }
dengan
V ( P 2 n ) = { z 1 , z 2 , ..., z 2 n } , V ( hK 1 ) = { x 1 , x 2 , · · · x h } , V ( N 2 ) = { y 1 , y 2 }
dan
E (( P 2 n ∪ hK 1 )(+) N 2 ) = E ( P 2 n ) ∪ { ( z 1 , y 1 ) , ( z 2 n , y 1 ) , ( z 1 , y 2 )( z 2 n , y 2 ) , ( x 1 , y 1 ) , ( x 2 , y 1 ) , · · · , ( x h , y 1 ) , ( x 1 , y 2 ) , ( x 2 , y 2 ) , · · · , ( x h , y 2 ) } .
Graf ini mempunyai 2 C 2 n +1 dan hC 4 .
Gambaran secara umum dari graf ( P 2 n ∪ hK 1 )(+) N 2 dapat dilihat pada Gam- bar 3.
30 Super Edge-Magic Pada Graf Yang Memuat Beberapa Cycle Ganjil
Teorema 2.4 Graf ( P 2 n ∪ hK 1 )(+) N 2 , n = 1 , 2 , 3 , · · · adalah graf super edge ma- gic.
Bukti Didefinisikan labeling f : V (( P 2 n ∪ hK 1 )(+) N 2 ) → { 1 , 2 , 3 , · · · , 2( n + 1) + h } sebagai berikut :
f ( r ) =              1 2( n + 1) + k ( n + 1) − R ( t/ 2) 2( n + 1) + k − u 2 n + s + 1 r = y 1 r = y 2 r = z t , t = 1 , 3 , 5 , ..., 2 n − 1 r = z u , u = 2 , 4 , 6 , ..., 2 n r = x s , s = 1 , 2 , 3 , ..., k .
Jelas bahwa f akan menyebabkan consecutive labeling pada setiap edge dari ( P 2 n ∪ hK 1 )(+) N 2 . Jadi ( P 2 n ∪ hK 1 )(+) N 2 adalah super edge-magic. Teorema 2.4 adalah pengembangan dari Teorema 2.2 (yang dihasilkan Sin-Min Lee dan A. Nien-Tsu Lee[8].Hal ini dapat ditunjukkan sebagai berikut: Ambil n = 1, Teorema 2.4 akan berbentuk ( P 2 n ∪ hK 1 )(+) N 2 dengan
V (( P 2 n ∪ hK 1 )(+) N 2 ) = { z 1 , z 2 , x 1 , x 2 , · · · , x h , y 1 , y 2 }
dan
E (( P 2 n ∪ hK 1 )(+) N 2 ) = { ( z 1 , z 2 ) , ( z 1 , y 1 ) , ( z 2 , y 1 ) , ( z 2 , y 2 ) , ( x 1 , y 1 ) , ( x 2 , y 1 ) , · · · ( x h , y 1 ) , ( x 1 y 2 ) , ( x 2 , y 2 ) , · · · ( x h , y 2 ) }
dimana keadaan ini sama dengan ( P 2 n ∪ hK 1 )(+) N 2 . Jadi Teorema 2.2 adalah keadaan khusus dari Teorema 2.4 dengan n = 1.
Contoh 2.5 Super edge-magic dari ( P 4 ∪ 3 K 1 )(+) N 2 dan ( P 6 ∪ 5 K 1 )(+) N 2 di- tunjukkan pada Gambar 3 dan Gambar ?? .

## 3. Range dari Konstanta Magic
Range dari konstanta magic yang akan dibahas disini adalah range dari total edge- magic labeling graph ( P 2 n ∪ hK 1 )(+) N 2 , n = 1 , 2 , 3 , · · · seperti yang ditunjukkan dalam teorema-teorema berikut :
Teorema 3.1 Graf ( P 2 n ∪ hK 1 )(+) N 2 , n = 1 , 2 , 3 , · · · adalah edge-magic total labeling dengan range dari konstanta magicnya.
10 n 2 + 5 h 2 + 27 n + 22 h + 14 nh + 25 2 n + 2 h + 3 6 k 6 14 n 2 + 13 h 2 + 45 n + 41 h + 28 nh + 29
2 n + 2 h + 3
Gambar 3: graf ( P 2 ∪ hK 1 )(+) N 2
Bukti Misalkan S v : jumlah —textitlabel vertex dan S e : jumlah label edge da- lam edge-magic total labeling f dengan konstanta magic h di G . Jumlah vertex di G adalah p = 2 n + h + 2 dan jumlah edge di G adalah q = 2 n + 2 h + 3, sehingga jumlah konstanta magic h di G adalah :
(2 n + 2 h + 3) k = 2 S v + S e + ( label ) z 1 + ( label ) z 2 n + h ( label ) y 1 + ( label ) y 2 = 1 + 2 + · · · + (4 n + 3 h + 5) + S v + ( label ) z 1 + ( label ) z 2 n + h ( label ) y 1 + ( label ) y 2 = (4 n + 3 h + 5)(4 n + 3 h + 6) 2 + S v + ( label ) z 1 + ( label ) z 2 n + h ( label ) y 1 + ( label ) y 2
Label kecil pada vertex S v = 1 + 2 + · · · + (2 n + h + 2) = (2 n + h + 2)(2 n + h + 3) 2 ambil label terkecil untuk y 1 , y 2 terkecil ya- itu 1 , 2 dan z 1 , z 2 n terkecil yang lain yaitu 3 , 4 sehingga persamaan menjadi :
(2 n +2 h +3) k > (4 n + 3 h + 5)(4 n + 3 h + 6) 2 + (2 n + h + 2)(2 n + h + 3) 2 +3 h +7
atau
k > 10 n 2 + 5 h 2 + 27 n + 22 h + 14 nh + 25 (2 n + h + 3)
Label besar pada vertex S v = (2 n +2 h +4)+((2 n +2 h +5)+ · · · +(4 n +3 h +5)
32 Super Edge-Magic Pada Graf Yang Memuat Beberapa Cycle Ganjil
= (2 n + h + 2)(6 n + 5 h + 9)
2
Ambil label terbesar untuk ( y 1 , y 2 ) terbesar yaitu ((4 n +3 h +5) , (4 n +3 h +4)) dan z 1 , z 2 n terbesar yang lain yaitu ((4 n + 3 h + 3) , (4 n + 3 h + 2)), sehingga Persamaan (3 . 1) menjadi :
(2 n + 2 h + 3) k 6 (4 n + 3 h + 5)(4 n + 3 h + 6) 2 +
(2 n + h + 2)(6 n + 5 h + 9) 2 + h (8 n + 6 h + 9) + (8 n + 6 h + 5)
atau
k 6 14 n 2 + 13 h 2 + 45 n + 41 h + 28 nh + 29 2 n + 2 h + 3
jadi
10 n 2 + 5 h 2 + 27 n + 22 h + 14 nh + 25
2 n + 2 h + 3 6 k 6 14 n 2 + 13 h 2 + 45 n + 41 h + 28 nh + 29
2 n + 2 h + 3

## 4. Kesimpulan
Dari uraian di atas maka dapat diambil kesimpulan yaitu :
1. Graf ( P 2 n ∪ hK 1 )(+) N 2 , n = 1 , 2 , 3 , · · · adalah super edge-magic
2. Super edge-magic planar graph ( P 2 ∪ hK 1 ) + N 2 adalah keadaan khusus dari ( P 2 n ∪ hK 1 )(+) N 2 dengan mengambil n = 1
3. Graf ( P 2 n ∪ hK 1 )(+) N 2 , n = 1 , 2 , 3 , · · · adalah edge-magic total labeling de- ngan range dari konstanta magic nya :
10 n 2 + 5 h 2 + 27 n + 22 h + 14 nh + 25 2 n + 2 h + 3 6 k 6 14 n 2 + 13 h 2 + 45 n + 41 h + 28 nh + 29
2 n + 2 h + 3

## Pustaka
[1] Chen, Z. , On super edge-magic graphs , The Journal of Combinatorial Ma- thematics and Combinatorial Computing, Vol. 38, 53-64, 2001.
[2] Craft, D., Tesar, E.H. , On a question by Erdos about edge-magic graphs , Discrete Mathematics, Vol. 207, 271-276, 1999.
[3] Enomoto, H., Llado, A.S., Nakawigawa, dan Ringel, G. , Super edge- magic graphs , SUT Journal of Mathematics, Vol. 43, No. 2, 105-109, 1998.
[4] Figueroa-Centeno, R.M., Ichishima,R. dan Muntaner-Batle, F.A. , The place of super edge-magic labelings among other classes of labelings , Di- screte Mathematics, Vol. 231, 153-168, 2001.
[5] Figueroa-Centeno, R.M., Ichishima,R. dan Muntaner-Batle, F.A. , On super edge-magic graphs , Ars Combinatoria, Vol. 64, 81-96, 2002.
[6] Godbold, R.P., Slater, P. , All cycles are edge-magic , Bull. Institute Com- binatoric Appl, Vol. 22, 93-97, 1998.
[7] Kotzig, A., Rosa, A. , Magic valuations of finite graphs , Canada Math. Bu- ll., Vol. 13, 451-461, 1970.
[8] Lee, S-M., Lee, N-T. A. , On Super Edge-Magic Graphs with Many Odd Cycles ,Congressus Numerantium, Vol. 163, 65 - 80, 2003.
[9] Yellen, J., Gross, J.L. , Graph Theory and ITS Aplication , 2nd ed., Cha- pman&Hall, USA, 2006.