PENGGABUNGAN PADA SUPER EDGE-MAGIC PETERSEN GRAPH DENGAN VERTEX PADA SETIAP VERTEX YANG ADA Ida Christiana1,Chairul Imron 2
ABSTRAK Pelabelan suatu graph adalah suatu pemetaan dari himpunan elemen graph (vertex, edge, atau vertex dan edge) terhadap bilangan bulat positif.. Salah satu jenis pelabelan graph adalah edge-magic total labeling adalah pelabelan graph yang mempunyai sifat penjumlahan dari semua label yang berhubungan dengan edge tersebut menghasilkan suatu konstanta, dan berlaku untuk edge yang lain pada graph tersebut. Sedangkan super edge-magic total labeling hampir sama dengan edge magic total labeling tetapi label dari vertex adalah bilangan integer positif terkecil yaitu {1, 2, ..., p}. Pada penelitian ini akan dikaji modifikasi super edge magic graph dari super edge magic graph yang sudah ada dengan cara menggabungkan sebuah Petersen Graph dengan vertex pada semua vertex yang terdapat pada Petersen Graph(n,2) dimana n 5 dengan operasi penggabungan, yaitu operasi penjumlahan . Selain itu juga ditentukan cara pelabelan serta mencari magic constant (bilangan ajaib) dari super edge magic graph yang baru. Kata kunci: edge magic graph, magic-sum,super edge magic graph
1.Pendahuluan Teori Graph saat ini sedang berkembang sangat pesat. Banyak sekali macam-macam bentuk Graph yang berkembang saat ini. Semakin banyak para ilmuwan membangun Graph-graph yang unik dan bermanfaat dalam penerapan kehidupan sehari-hari. Graph adalah suatu himpunan yang terdiri dari simpul (vertex) dan sisi (edge). Diantara himpunan-himpunan tersebut terdapat himpunan bagian yang juga merupakan Graph yang disebut subGraph. Berbagai masalah dalam graph, salah satunya adalah labeling Graph.Semua graph memenuhi terbatas, undirected, dan simple. Selalu dinotasikan jumlah vertex dan jumlah edge dinotasikan dengan V (G ) dan E (G ) . Symbol A selalu dinotasiakan sebuah bilangan cardinal dari set A . Edge-magic total labeling pada G adalah bijection f dari V (G ) E (G ) onto 1,2,..., V (G) E (G) dengan syarat tersebut , dapat memberikan uv f (u ) f (v ) f (uv ) k untuk k konstan, itu dapat dinyatakan f (u ) f (v ) f (uv) k edge sum pada uv dan k magic sum pada f .
Seminar Nasional-Pendidikan Sains FMIPA Unesa 2008/255
Petersen Graph P(n,2) adalah edge-magic total.Fukuchi menunjukkan bahwa Petersen Graph P(n,2) adalah super edge-magic total. Pada edge-magic total labeling f dikatakan sebagai super edge-magic total jika f (V (g )) 1, 2,..., V (G) dan f ( E (G)) V (G ) 1, V (G) 2,....., V (G) E (G) . Dalam makalah ini penulis akan membahas Petersen Graph yang ditambahkan vertex pada setiap bagian vertexnya tetap memenuhi syarat super edge-magic total. 2.Pembahasan n 1 Sebuah Petersen Graph P(n,m), n 3 dan 1 m 2 konsis pada semua n cycle v1 , v 2 ,..., v n adalah sebuah set pada n bentuk vi zi , 1 i n ,dan edge yang didalam zi zi m ,1 i n ,dengan indikasi dari modulo n. Untuk n 5 ,m = 2 dan p 1 , kita notasikan dengan P (n,2) A p untuk sebuah Graph dimana dipilih salah satu untuk menambahakn p vertex dan p edge pada satu dari vertex P(n,2), kita sebut v1 . Dimana V P n,2A p V ( P( n,2)) {u j : 1 j p} dan E ( P (n,2) A p ) E ( P( n,2)) {v1u j : 1 j p}
Teorema 2.1 Untuk n ganjil, n 5 dan p 1 , untuk graph P( n,2) A p adalah super edge-magic total labeling Bukti : Diberikan sebuah pemetaan, f :V P( n,2) A p 1,2,...,2n pdimana n i f (v i ) 2 3n i 2 n i 4 4 2n i 4 f ( zi ) 4 3n i 4 4 4n i 4 4
jika i untuk semua ,2 i n 1 jika i ganjil ,1 i n jika i 1 mod 4 jika i 2 mod 4 jika i 3 (mod 4) jika i 0 (mod 4)
f (u j ) 2n j untuk 1 j p
Dari labeling diatas telah dibuktikan bahwa P( n,2) A p adalah super edge-magic total labeling dengan 11n 3 k= 2 p 2
Seminar Nasional-Pendidikan Sains FMIPA Unesa 2008/256
Dalam makalah ini penulis mengembangkan dari teorema diatas dengan menambahkan vertex pada vertex dibagian luar, vertex dibagian dalam dan vertex dibagian luar-dalam. Teorema 2.2 Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian luar) dengan n = 5 dan p 1 adalah super edge magic graph. Bukti : .Didefinisikan labeling f : V ( P( n,2) Ap ) {1, 2,3,...,3n} adalah: i untuk semua nilai i , 2 i n 1 n f (v i ) 2 3n i untuk nilai i ganjil ,1 i n 2 n i 4 jika i 1 mod 4 4 2n i 4 jika i 2 mod 4 4 f ( zi ) 3n i 4 jika i 3 (mod 4) 4 4n i 4 jika i 0 (mod 4) 4 2n j , untuk j 1 f (u j ) 3n 2 j , untuk nilai i diantara 2 j p Dari labeling diatas telah dibuktikan bahwa Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian luar) dengan n = 5 adalah super edgemagic total labeling dengan 19n 17 k= 2 Teorema 2.3 Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian dalam) dengan n ganjil n = 5 dan p 1 adalah super edge magic graph. Bukti : Didefinisikan labeling f : V ( P( n,2) Ap ) {1, 2,3,...,3n} adalah: 4n 1 i f (v i ) 2 4n 6 i 2 i n f ( zi ) 2 3n i 2
untuk nilai i ganjil untuk nilai i genap
untuk semua nilai i , 2 i n 1 untuk nilai i ganjil ,1 i n
Seminar Nasional-Pendidikan Sains FMIPA Unesa 2008/257
n j 4 jika j 1 mod 4 4 2n j 4 jika j 2 mod 4 4 f (u j ) 3n j 4 jika j 3 (mod 4) 4 4n j 4 jika j 0 (mod 4) 4 Dari labeling diatas telah dibuktikan bahwa Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian luar) dengan n = 5 adalah adalah super edge-magic total labeling dengan 17n 3 k= 2 Teorema 2.4 Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian dalam dan luar) dengan n = 5 dan p 1 adalah super edge magic graph. Didefinisikan labeling f : V ( P( n,2) Ap ) {1, 2,3,...,3n} adalah: 4n 1 i untuk i ganjil 2 f (v i ) 4n 6 i untuk i genap 2 i untuk semua nilai i , 2 i n 1 n f ( zi ) 2 3n i untuk nilai i ganjil ,1 i n 2 n j 4 jika j 1 mod 4 4 2n j 4 jika j 2 mod 4 4 f (u j ) 3n j 4 jika j 3 (mod 4) 4 4n j 4 jika j 0 (mod 4) 4 Dari labeling diatas telah dibuktikan bahwa Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian luar dan dalam) dengan n = 5 adalah super edge-magic total labeling dengan k=
21n 3 2
Seminar Nasional-Pendidikan Sains FMIPA Unesa 2008/258
3.Kesimpulan Super edge magic graph baru yang terbentuk dengan operasi disajikan dalam tabel di bawah ini dengan bilangan ajaibnya. Super Edge Magic Graph Baru Bilangan Ajaib Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian luar) Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian dalam) Graph Petersen graph P(n,2) Ap (penambahan vertex pada vertex bagian luar dan dalam)
k=
19n 17 2
k=
17 n 3 2
k=
21n 3 2
4.Daftar Pustaka Baskoro, E. T., dkk. (2004), “Expanding Super Edge-Magic Graph”, J. Indones. Math. Soc. (MIHMI), Vol 36 No. 2, hal. 177-125. Enomoto, H.,Llado, A.S.,Nakamigawa, T. & Ringel , G.,”Super edge-magic graph”,SUT J.Math. Vol 34 (1998).pp. 105-109 Fukuchi, Y.,”Edge-magic labelings of generalized Petersen graph P(n,2)”,Ars Combin. 59 (2001),pp. 253-257. Wallis W.D., dkk, (2000) “Edge-magic total labelings”, Australasian J. Combin. , 22 177-190.
Seminar Nasional-Pendidikan Sains FMIPA Unesa 2008/259
