Vol. 7, No. 1, Juni 2012
VERTEX ANTIMAGIC TOTAL LABELING PADA GRAPH MULTICYCLE Dominikus Arif Budi Prasetyo Program Studi Pendidikan Matematika Jurusan MIPA Fakultas Pendidikan dan Ilmu Keguruan Universitas Sanata Dharma Yogyakarta Paingan, Maguwoharjo, Depok, Sleman.
[email protected] Abstrak Pelabelan graf merupakan bagian dari graf yang berkembang saat ini. Jenis pelabelan pada graf bergantung pada domainnya, yakni pelabelan sisi ajaib, pelabelan titik ajaib, dan pelabelan total ajaib. Pelabelan total ajaib pada graf dibedakan lagi berdasarkan komponen graf yang dievaluasi, yakni pelabelan total sisi ajaib dan pelabelan total titik ajaib. Pada pelabelan ajaib, bobot dari komponen graf yang dievaluasi adalah sama, jika bobotnya tidak sama maka dinamakan pelabelan tak-ajaib (antimagic). Misalkan G adalah graf dengan banyak titik p dan sisi q. Suatu pemetaan bijektif dari komponen-komponen graf ke bilangan bulat positif {1, 2, …, (p+q)} disebut called (a, d) vertex antimagic total labelling (pelabelan total titik ajaib) dari graf G jika bobot setiap titik (vertex) merupakan barisan aritmetika naik. Pada artikel ini membahas bahwa graf multicycle mCp memenuhi (a, d) vertex antimagic total labelling dan beberapa bentuk pelabelannya. Kata kunci : graph multicycle, vertex antimagic total labeling Abstract Labeling graph is a subject in graph which is growing up nowadays. The kind of labeling graph is based on its domain, they are edge magic labeling, vertex magic labeling and total magic labeling. Total magic labeling graph can be differentiated based on graph component which is evaluated, they are edge magic total labeling and vertex magic total labeling. In magic labeling, the weight of the evaluated graph’s component is equal. If the weight isn’t equal, it is called antimagic labeling. Let G is graph with p vertex and q edge. A bijective mapping from components of graph to positive integer {1, 2, …, (p+q)} is called (a, d) vertex antimagic total labeling of (p,q)-graph G if the weight of the vertex is an increase aritmethic series. In this case, odd cycle Cp with p > 3 satisfy vertex antimagic total labeling. This article observes how multicycle graph mCp satisfy (a, d) vertex antimagic total labeling. The result of this observation is that mCp satisfy (a, d) vertex antimagic total labeling, the boundary and the pattern of its labeling. Keywords : graph multicycle, vertex antimagic total labeling.
PENDAHULUAN
labeling), atau keduanya (total labeling).
Graph merupakan salah satu cabang
Beberapa
matematika yang sangat berkembang
labeling dengan menggeneralisasi ide
pesat. Salah satu bagiannya adalah graph
dari persegi ajaib. Penelitian ini pertama
labeling atau pelabelan graph. Di sini
kali dilakukan oleh Kotzig dan Rosa
graph yang dipakai adalah terbatas,
(1970). Sedangkan vertex magic total
sederhana dan tidak berarah. Suatu
labeling pertama kali dikenalkan oleh
pelabelan graph
MacDougal, dkk (2002). Vertex magic
membawa himpunan
peneliti
dari vertex atau edge atau keduanya ke
total
labeling
himpunan bilangan bulat positif. Jenis
pemetaan bijektif
memperkenalkan
didefinisikan
sebagai
dari labeling tergantung pada domainnya,
f : V (G ) E (G ) {1, ,2,, p q} dengan
yaitu vertex (vertex labeling), edge (edge
konstanta h sedemikian hingga untuk 57
Vertex Antimagic Total Labeling........(Dominikus Arif Budi Prasetyo)
setiap
vertex
memenuhi
u V (G )
f (u ) f (uv ) h dengan v semua vertex
yang adjacent dengan u dan v V (G ) . Konsep
antimagic
graph
diperkenalkan oleh Hartsfield dan Ringel (1990).
Suatu
antimagic
labeling
merupakan edge labeling dari suatu
labeling
Selanjutnya
Bodendiek
dan
Walther
(1993) mendefinisikan konsep (a, d) antimagic labeling sebagai suatu edge
dengan
domain
gabungan himpunan vertex dan himpunan edge). Untuk pengkajian masalah dalam artikel ini akan digunakan total labeling. Berikut
diberikan
beberapa
definisi
tentang labeling. Definisi 1. (Wallis, 2001) Vertex magic total labeling dari
graph dengan bilangan bulat {1,2,, q} sehingga bobot setiap vertex berbeda.
(labeling
(p, q)-graph, G, adalah pemetaan bijektif f : V (G ) E (G ) {1,2,, p q}
sedemikian hingga untuk setiap u V (G ) berlaku
f (u ) f (uv ) h untuk semua
yang
adjacent
dengan
u.
labeling dengan bobot semua vertex
v V (G )
membentuk
naik
Bilangan h disebut magic constant.
dengan suku pertama a dan beda d. Pada
Graph yang memenuhi vertex magic total
artikel ini membahas bentuk multicycle
labeling disebut vertex magic total graph.
graph (mCp, yakni gabungan beberapa
Jika label dari vertex pada vertex
cycle graph yang identik, kemudian
magic total graph adalah bilangan integer
menentukan keberlakuan dan mencari
yang terkecil yaitu {1, ,2,, p q} maka
pola (a,d) VATL pada multicycle graph
labelingnya disebut super vertex magic
(mCp).
total labeling dan graphnya disebut super
barisan
aritmetika
vertex magic total graph. Definisi 2. (Wallis, 2001)
PEMBAHASAN
Super vertex magic total labeling
Labeling Graph Labeling graph adalah pemetaan bijektif
yang
memetakan
komponen graph tersebut
semua ke suatu
himpunan bilangan positif. Ada beberapa macam labeling, yaitu vertex labeling (labeling
dengan
domain
himpunan
vertex), edge labeling (labeling dengan domain 58
himpunan
edge)
dan
total
dari (p, q)-graph, G, adalah pemetaan bijektif
f : V (G ) E (G ) {1,2,, p q}
sedemikian hingga untuk setiap u V (G ) berlaku
f (V (G )) {1,2,, p}
dan
f (u ) f (uv ) h untuk semua v V (G )
yang adjacent dengan u. Bilangan h disebut magic constant. Graph yang memenuhi super vertex magic total
Vol. 7, No. 1, Juni 2012
labeling disebut super vertex magic total
antimagic total labeling atau (a, d)VATL
graph.
pada cycle. Jika pada vertex magic total
labeling
menghasilkan
bobot
4
setiap 1
vertex yang tidak sama untuk setiap vertex u dan vertex v merupakan vertex
2
5
6
3
yang adjacent dengan vertex u maka (a)
labelingnya disebut vertex antimagic total labeling. 3
Definisi 3. (Baca, dkk., 2003) Suatu
pemetaan
bijektif
f : V (G ) E (G ) {1,2,, p q}
8
5
6
2
disebut
vertex antimagic total labeling dari (p,
1
q)-graph G jika bobot dari vertex w f ( u ) f (u ) f (uv ) , untuk setiap dan
4
7
(b) Gambar 1.
(a) : (7, 2) VATL dan (b) : (11, 2) VATL.
v V (G ) yang adjacent dengan u semua-
nya berbeda. Jika bobot-bobot vertex
Vertex Antimagic Total Labeling pada
pada vertex antimagic total labeling
Multicycle Graph (mCp
membentuk suatu barisan aritmetika naik
Pada bagian ini adalah hasil dari
dengan suku pertama a dan beda d maka
pengembangan peneliti mengenai vertex
pelabelannya
antimagic total labeling pada multicycle
disebut
(a,
d)
vertex
graph (mCp. Pertama, akan dibahas
antimagic total labeling.
mengenai basic counting untuk menentu-
Definisi 4. (Baca, dkk., 2003)
kan batasan suku pertama a dan beda d
Suatu pemetaan bijektif f : V (G ) E (G ) {1,2,, p q}
dari vertex antimagic total labeling pada disebut
multicycle graph (mCp. Kedua, akan
(a, d) vertex antimagic total labeling dari
dibahas
(p, q)-graph G jika bobot dari semua
(mCp yang memenuhi vertex antimagic
vertex membentuk barisan aritmetika
total labeling.
naik dengan suku pertama a dan beda d
mengenai
multicycle
graph
Pada multicycle graph (mCp,
W {w f (u ) | u V } {a, a d , a 2d ,, a p 1d }setiap cycle memiliki p buah vertex dan p
.Sebagai contoh, diberikan ilus-trasi pada
buah edge sehingga multicycle graph
Gambar 1 berikut, yaitu (a, d) vertex
memiliki mp buah vertex ( | V | mp ) dan mp buah edge ( | E | mp ). 59
Vertex Antimagic Total Labeling........(Dominikus Arif Budi Prasetyo)
v1,5
v2,5
v1,6
v1,4
graph ke-1
v2,6
v1,3
v1,1
v2,4
;
v1,p
vm,5
graph ke-2 v2,3
v2,1
vm,4
----
v2,p
v1,2
vm,6
graph ke-3 vm,p
v2,2
vm,3
vm,1
vm,2
Gambar 2. Multicycle Graph (mCp
Jumlah total dari vertex dan edge
labeling dengan a 6 dan d 6 untuk
adalah 2mp ( | V | | E | 2mp ). Misalkan
semua m 1 dan p 3 .
Sw adalah jumlah semua bobot vertex, Sv
Bukti :
adalah jumlah semua label vertex, dan Se
Karena pelabelan dimulai dari angka 1
adalah jumlah semua label edge. Bobot
maka bobot vertex terkecil adalah 6, yaitu
vertex pada multicycle graph adalah
jumlahan label satu vertex dan dua edge
jumlahan dari label vertex dan dua edge
yang insident dengan vertex tersebut
yang insident dengan vertex tersebut.
ambil label-labelnya 1, a 1 2 3 6 .
Sv 2Se Sw (Sv Se) Se a(ad)(a2d)(a(mp1)d) mp(2mp1) Se (mp)a (
2, dan 3 atau
mp(mp1) )d 2
(3.1)
Berikut ini diberikan Teorema-
Bobot vertex yang paling besar adalah a (mp 1)d 2mp (2mp 1) (2mp 2) Untuk a = 6 diperoleh 6 (mp 1)d 6mp 3
teorema hasil pengembangan peneliti
d
tentang (a, d) vertex antimagic total labeling pada multicycle graph. Teorema pertama tentang batas nilai a dan d agar
6mp 9 6 mp 1
Jadi untuk sebarang m 1 dan p 3 diperoleh a 6 dan d 6 .
□
multicycle graph memenuhi (a, d) vertex
Hasil selanjutnya adalah teorema
antimagic total labeling untuk semua
yang menunjukkan bahwa multicycle
m 1 dan p 3 .
graph memenuhi VATL.
Teorema 1.
Teorema 2.
Setiap multicycle graph (mCp) mempunyai (a, d) vertex antimagic total 60
Pada multicycle (mCp) terdapat (2mp + 2, 1) VATL untuk m 1 dan p 3 .
Vol. 7, No. 1, Juni 2012
Bukti : Konstruksi
multicycle
sehingga S e
graph
Untuk d = 1 maka Persamaan (3.1)
(mCp) dengan label vertex ke-j dari graph ke-i
(xi,j)
dengan
i 1, 2,..., m
mp (mp 1) . 2
menjadi
dan
j 1, 2,..., p sebagai berikut :
mp(2mp 1)
f ( xi, j ) p (2m i ) j
mp(mp 1) mp(mp 1) (mp)a ( ) 2 2 5mp 3 2a mp 1 a 2mp 2
Sedangkan label dari edgenya adalah
Jadi terbukti multicycle graph memnuhi
f ( xi , j xi , j 1 ) ip j 1, j 1,2, , p 1
(2mp + 2, 1) VATL untuk m 1 dan p 3
dan
. □
f ( xi ,1 xi , p ) p(i 1) 1 Dari konstruksi pelabelan tersebut
Sebagai ilustrasi dari Teorema 2 diberikan
berakibat label-label edgenya {1,2,, mp}
(20, 1)VATL untuk 3C3.
18
15
2
3
untuk
merupakan contoh pelabelan multicycle
{( mp 1), ( mp 2), ,2mp}
16
pelabelan
beberapa multicycle. Pada Gambar 3
dan label-label vertexnya
1
contoh
17
4
13
12
5
6
14
7
10
8
9
11
Gambar 3. (20, 1) VATL untuk 3C3 Teorema selanjutnya diberikan untuk
untuk p ganjil
VATL pada multicycle dengan d = 2.
p1 ; j 1,2,, 2p i 1 4j 3 2 p1 p1 f xi, j 2p i 1 4 j 1 ; j 1,, p1 ; p3 2 2 2p mi 2p3 ; j p
Teorema 3. Pada multicycle graph (mCp) juga mempunyai (2mp + 3, 2) VATL untuk m 1 dan p 3 .
Bukti : Konstruksi (mCp)
multicycle
graph
untuk p genap
dengan label vertex ke-j dari
graph ke-i (xi,j) sebagai berikut : 61
Vertex Antimagic Total Labeling........(Dominikus Arif Budi Prasetyo)
2 p i 1 1 f xi , j 2 p i 1 2 p j 3 2 p m i 2 p j 3
; j 1 ; j 2, , p 2 ; j p 1, p
dengan
i 1, 2, , m
.
Sedangkan label-label edgenya sebagai berikut : untuk p ganjil p 3, 7,11,
2 p ( m i ) 2 j f ( xi, j xi, j 1 ) 2 p(i 1) 2 j 2 p(i 1) 2 j
; j 1,3, , p 3 ; j 2, 4, p 2
dan
; j p 1
f ( xi,1 xi, p ) 2ip
dan p 5,9,13, 3 p 1 2 p ( m i ) j 1 2 2 p (i 1) p 1 2 2 f ( xi, j xi, j 1 ) 2 pi p5 2 p (m i) ( p 1) 2( j 2 ) 2 p (i 1) p 1 2 2 f ( xi,1 xi, p ) 2ip
p 1 2 p 1 ; j 2, 4, , 2 p 3 ; j 2 p5 p9 ;j , ,, p 2 2 2 p 7 p 11 ;j , , , p 1 2 2 ; j 1,3, ,
dan
untuk p genap 2 p ( m i ) 2 j f ( xi, j xi, j 1 ) 2 p(i 1) 2 j 2 p(i 1) 2 j f ( xi,1 xi, p ) 2ip i 1, 2, , m
; j 1,3, , p 3 ; j 2, 4, p 2
dan
; j p 1
xi,jxi,j+1
Dari pelabelan di atas, diperoleh
merupakan edge yang menghubungkan
semua label vertex berupa bilangan ganjil
vertex ke-j dan vertex ke-(j+1) dari graph
dan semua label edge berupa bilangan
ke-i serta xi,1xi,p merupakan edge yang
genap.
dengan
dan
menghubungkan vertex ke-1 dan vertex ke-p dari graph ke-i. 62
mp
Jumlah
semua
S v (2i 1) (mp ) 2 i 1
label
vertex
Vol. 7, No. 1, Juni 2012
dan
jumlah
semua
label
edge
beberapa multicycle. Pada Gambar 4 merupakan contoh pelabelan (27, 2)VATL
mp
S e 2i mp(mp 1) . Karena bobot
untuk 3C4.
i 1
tiap
vertex
dari
multicycle
SIMPULAN
graph
Dari pembahasan di atas dapat
(mCp) adalah w(x) = f(x) + f(xy) + f(xz)
disimpulkan
dengan y dan z merupakan vertex-vertex
bahwa
pada
multicycle
graph (mCp, yakni gabungan beberapa
yang adjacent dengan x, diperoleh bobot
cycle graph yang identik (a,d) VATL.
vertex semuanya bilangan ganjil.
a. Setiap
Untuk d = 2, Persamaan (3.1)
multicycle
graph
(mCp)
mempunyai (a, d) vertex antimagic
menjadi
mp(mp1) mp(2mp1) mp(mp1) (mp)a ( )2 2 3mp 2 a mp1 a 2mp3
total labeling dengan a 6 dan d 6 untuk semua m 1 dan p 3 .
b. Pada multicycle (mCp) terdapat (2mp + 2, 1) VATL untuk m 1 dan p 3 . c. Pada multicycle graph (mCp) juga
Jadi terbukti bahwa pada multicycle
mempunyai (2mp + 3, 2) VATL
(mCp) terdapat (2mp + 3, 2) VATL untuk
untuk m 1 dan p 3 .
□
m 1 dan p 3 .
Sebagai ilustrasi dari Teorema 3 diberikan
contoh
19
pelabelan
22
21
8
11
4
1
18
untuk 14
16
7
9
13
12
10
15
3
6
24
17
5
20
2
23
Gambar 4 (27, 2) VATL pada 3C4. Dalam
artikel
ini
telah
dibahas
keberlakuan (a,d) VATL pada multicycle
yang berlaku atau keberlakuannya pada gabungan graph yang lain.
graph (mCp) untuk d = 1 dan d = 2. Pembaca dapat meneliti untuk nilai d lain 63
Vertex Antimagic Total Labeling........(Dominikus Arif Budi Prasetyo)
DAFTAR PUSTAKA Baca, M., dkk. (2003). Vertex Antimagic Total Labeling of Graph. Discuss. Math. Graph Theory, 23, 67 – 83.
Bodendiek, R. dan Walther, G. (1993). Arithmetisch
Antimagische
Graphen. Dalam Wagner, K. dan Bodendiek, R., Graphentheorie III, Mannheim : BI – Wiss. Verl. Hartsfield, N. dan Ringel, G. (1990). Pearls in Graph Theory. Boston : Academic Press. Kotzig, A. dan Rosa, A. (1970). Magic Valuations
of
Finite
Graphs.
Canad. Math Bull, 13, 451 – 461. MacDougall, J.A., dkk. (2002). Vertex Magic Total Labelings of Graphs. Util. Math, 61, 3 – 21. Wallis, W.D. (2001). Magic Graph, Boston : Birkhauser.
64
