## 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. dominic_abp@yahoo.co.id

## 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 m C p 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 C p with p >  3  satisfy  vertex  antimagic  total  labeling. This  article  observes  how  multicycle graph m C p satisfy ( a , d ) vertex antimagic total labeling. The result of this observation is that m C p satisfy ( a , d ) vertex antimagic total labeling, the boundary and the pattern of its labeling.
Keywords : graph multicycle, vertex antimagic total labeling.

## PENDAHULUAN
Graph merupakan  salah  satu  cabang matematika  yang  sangat  berkembang pesat. Salah satu bagiannya adalah graph labeling atau  pelabelan graph .  Di  sini graph yang  dipakai  adalah  terbatas, sederhana  dan  tidak  berarah.  Suatu pelabelan graph membawa  himpunan dari vertex atau edge atau  keduanya  ke himpunan  bilangan  bulat  positif.  Jenis dari labeling tergantung pada domainnya, yaitu vertex ( vertex labeling ), edge ( edge
labeling ),  atau  keduanya  ( total  labeling ). Beberapa peneliti memperkenalkan labeling dengan  menggeneralisasi  ide dari  persegi  ajaib.  Penelitian  ini  pertama kali  dilakukan  oleh  Kotzig  dan  Rosa (1970).  Sedangkan vertex  magic  total labeling pertama  kali  dikenalkan  oleh MacDougal,  dkk  (2002). Vertex  magic total labeling didefinisikan sebagai pemetaan bijektif
} , , 2 , , 1 { ) ( ) ( : q p G E G V f     dengan konstanta h sedemikian  hingga  untuk
setiap vertex ) ( G V u  memenuhi
h uv f u f   ) ( ) ( dengan v semua vertex yang adjacent dengan u dan ) ( G V v  .
Konsep antimagic graph diperkenalkan oleh Hartsfield dan Ringel (1990). Suatu antimagic labeling merupakan edge  labeling dari  suatu graph dengan  bilangan  bulat } , , 2 , 1 { q  sehingga  bobot  setiap vertex berbeda.
Selanjutnya  Bodendiek  dan  Walther (1993)  mendefinisikan  konsep  ( a , d ) antimagic  labeling sebagai  suatu edge labeling dengan  bobot  semua vertex membentuk barisan aritmetika naik dengan suku pertama a dan  beda d .  Pada artikel  ini  membahas  bentuk multicycle graph ( m C p  ,  yakni  gabungan  beberapa cycle graph yang  identik,  kemudian menentukan  keberlakuan  dan  mencari pola  ( a,d ) VATL pada multicycle graph ( m C p ).

## PEMBAHASAN
Labeling Graph
Labeling  graph adalah  pemetaan bijektif yang memetakan semua komponen graph tersebut    ke  suatu himpunan bilangan positif.  Ada beberapa macam labeling ,  yaitu vertex labeling ( labeling dengan  domain  himpunan vertex ), edge labeling ( labeling dengan domain  himpunan edge )  dan total
labeling ( labeling 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 ( p , q )- graph , G , adalah pemetaan bijektif
} , , 2 , 1 { ) ( ) ( : q p G E G V f    
sedemikian  hingga  untuk  setiap ) ( G V u  berlaku h uv f u f   ) ( ) ( untuk  semua ) ( G V v  yang adjacent dengan u . Bilangan h disebut magic  constant . Graph yang memenuhi vertex magic total labeling disebut vertex magic total graph . Jika  label  dari vertex pada vertex magic total graph adalah bilangan integer yang  terkecil  yaitu } , , 2 , , 1 { q p   maka labeling nya  disebut super  vertex  magic total labeling dan graph nya disebut super vertex magic total graph .
Definisi 2. (Wallis, 2001)
Super  vertex  magic  total  labeling dari  ( p , q )- graph , G ,  adalah  pemetaan bijektif } , , 2 , 1 { ) ( ) ( : q p G E G V f     sedemikian  hingga  untuk  setiap ) ( G V u  berlaku } , , 2 , 1 { )) ( ( p G V f   dan h uv f u f   ) ( ) ( untuk  semua ) ( G V v  yang adjacent dengan u .  Bilangan h disebut magic  constant . Graph yang memenuhi super  vertex  magic  total
labeling disebut super  vertex  magic  total graph .
Jika  pada vertex  magic  total labeling menghasilkan  bobot  setiap
vertex yang  tidak  sama  untuk  setiap vertex  u dan vertex  v merupakan vertex yang adjacent dengan vertex  u maka
labeling nya  disebut vertex  antimagic total labeling .
Definisi 3. (Baca, dkk., 2003) Suatu pemetaan bijektif } , , 2 , 1 { ) ( ) ( : q p G E G V f     disebut
vertex  antimagic  total  labeling dari    ( p , q )- graph  G jika  bobot  dari vertex ) ( ) ( ) ( uv f u f u w f   ,  untuk  setiap  dan
) ( G V v  yang adjacent dengan u semua- nya  berbeda.  Jika  bobot-bobot vertex pada vertex  antimagic  total  labeling membentuk suatu barisan aritmetika naik dengan suku pertama a dan  beda d maka pelabelannya  disebut  ( a , d ) vertex antimagic total labeling .
Definisi 4. (Baca, dkk., 2003)
Suatu pemetaan bijektif
} , , 2 , 1 { ) ( ) ( : q p G E G V f     disebut ( a , d ) vertex antimagic total labeling dari ( p , q )- graph  G jika  bobot  dari  semua vertex membentuk  barisan  aritmetika naik  dengan  suku  pertama a dan  beda d   } 1 , , 2 , , { } | ) ( { d p a d a d a a V u u w W f         .Sebagai contoh, diberikan ilus-trasi pada Gambar  1  berikut,  yaitu  ( a , d ) vertex
antimagic  total  labeling atau  ( a , d ) VATL pada cycle . (a) (b)
Gambar 1.  (a) : (7, 2) VATL dan (b) :
(11, 2) VATL.
Vertex  Antimagic  Total  Labeling  pada Multicycle Graph (mC p 
Pada  bagian  ini  adalah  hasil  dari pengembangan  peneliti  mengenai vertex antimagic  total  labeling pada multicycle graph ( m C p  .  Pertama,  akan  dibahas mengenai basic counting untuk menentu- kan  batasan  suku  pertama a dan  beda d dari vertex  antimagic  total  labeling pada multicycle  graph ( m C p  .  Kedua,  akan dibahas mengenai multicycle  graph
( m C p  yang  memenuhi vertex  antimagic total labeling .
Pada multicycle  graph ( m C p  , setiap cycle memiliki p buah vertex dan p buah edge sehingga multicycle  graph memiliki mp buah vertex ( mp V  | | )  dan mp buah edge ( mp E  | | ). 4 1 2 3 5 6 7 8 4 1 2 3 5 6
Jumlah  total  dari vertex dan edge adalah  2 mp ( mp E V 2 | | | |   ).  Misalkan
S w adalah jumlah semua bobot vertex , S v adalah  jumlah semua  label vertex , dan S e adalah  jumlah  semua  label edge .  Bobot vertex pada multicycle  graph adalah jumlahan  dari  label vertex dan  dua edge yang insident dengan vertex tersebut.
Berikut  ini  diberikan  Teorema- teorema  hasil  pengembangan  peneliti tentang  ( a , d ) vertex  antimagic  total labeling pada multicycle graph . Teorema pertama tentang    batas nilai a dan d agar multicycle  graph memenuhi  ( a , d ) vertex antimagic  total  labeling untuk  semua 1  m dan 3  p .
Teorema 1.
Setiap multicycle  graph ( m C p ) mempunyai  ( a , d ) vertex  antimagic  total
labeling dengan 6  a dan 6  d untuk semua 1  m dan 3  p .

## Bukti :
Karena  pelabelan  dimulai  dari  angka  1 maka bobot vertex terkecil adalah 6, yaitu jumlahan  label  satu vertex dan  dua edge yang insident dengan vertex tersebut ambil  label-labelnya  1,    2,  dan  3  atau
6 3 2 1     a .
Bobot vertex yang paling besar  adalah
Untuk a = 6 diperoleh 6 1 9 6 3 6 ) 1 ( 6         mp mp d mp d mp Jadi  untuk  sebarang 1  m dan 3  p diperoleh 6  a dan 6  d . □
Hasil  selanjutnya  adalah  teorema yang  menunjukkan  bahwa multicycle graph memenuhi VATL .
Teorema 2.
Pada multicycle ( m C p ) terdapat (2 mp + 2,
1) VATL untuk 1  m dan 3  p . graph ke-1 ; graph ke-2 - - - - graph ke-3 v 1,1 v 1,3 v 1,4 v 1,5 v 1,6 v 1, p v 1,2 v 2,1 v 2,3 v 2,4 v 2,5 v 2,6 v 2, p v 2,2 v m ,1 v m ,3 v m ,4 v m ,5 v m , 6 v m , p
v m ,2
Gambar 2. Multic ycle Graph ( m C p 
) ) 1 ( ( ) 2 ( ) ( ) ( 2 d mp a d a d a a S S S S S S e e v w e v               (3.1) ) 2 ) 1 ( ( ) ( ) 1 2 ( d mp mp a mp S mp mp e      ) 2 2 ( ) 1 2 ( 2 ) 1 (        mp mp mp d mp a

## Bukti :
Konstruksi multicycle    graph ( m C p ) dengan label vertex ke- j dari graph ke- i ( x i , j ) dengan 1, 2,..., i m  dan 1, 2,..., j p  sebagai berikut :
j i m p x f j i    ) 2 ( ) ( ,
Sedangkan label dari edge nya adalah
Dari  konstruksi  pelabelan  tersebut berakibat  label-label edge nya } , , 2 , 1 { mp  dan label-label vertex nya
} 2 , ), 2 ( ), 1 {( mp mp mp    sehingga
2 ) 1 (   mp mp S e .
Untuk d =  1  maka  Persamaan  (3.1)
menjadi 2 2 1 2 3 5 ) 2 ) 1 ( ( ) ( 2 ) 1 ( ) 1 2 (             mp a mp a mp mp mp a mp mp mp mp mp
Jadi  terbukti multicycle  graph memnuhi (2 mp + 2, 1) VATL untuk 1  m dan 3  p . □
Sebagai  ilustrasi  dari  Teorema  2 diberikan contoh pelabelan untuk beberapa multicycle .  Pada  Gambar  3 merupakan  contoh  pelabelan multicycle
(20, 1) VATL untuk 3C 3 .
Gambar 3. (20, 1) VATL untuk 3C 3
Teorema  selanjutnya  diberikan  untuk
VATL pada multicycle dengan d = 2.
Teorema 3.
Pada multicycle graph ( m C p ) juga mempunyai  (2 mp +  3,  2) VATL untuk
1  m dan 3  p .
Bukti :
Konstruksi multicycle graph ( m C p )    dengan  label vertex ke- j dari
graph ke- i ( x i , j ) sebagai berikut :
untuk p ganjil
        , 1 2 1 4 3                    ; 1,2, , 2 1 1 2 1 4 1    ; 1, , 1   ; 3 2 2 2
2 3                  ;
i j p p i j j p p f x p i j j p p p m i p j p
                                  
  untuk p genap 1 2 3 16 17 18 4 5 6 13 14 15 7 8 9 10 11 12 1 ) 1 ( ) ( dan 1 , , 2 , 1 , 1 ) ( , 1 , 1 , ,         
i p x x f p j j ip x x f p i i j i j i 
            , 2 1 1
; 1 2 1 2 3 ; 2, , 2 ; 1, 2 2 3 i j p i j f x p i p j j p
j p p p m i p j    
                  dengan 1, 2, , i m   .
Sedangkan label-label edge nya sebagai berikut :
untuk p ganjil 3, 7,11, p   ip x x f p j j i p p j j i p p j j i m p x x f
p i i j i j i 2 ) ( dan 1 ; 2 ) 1 ( 2 2 , 4 , 2 ; 2 ) 1 ( 2 3 , , 3 , 1 ; 2 ) ( 2 ) ( , 1 , 1 , ,                      
dan 5, 9,13, p   ip x x f p p p j p i p p p p j p j p i m p p j pi p j p i p p j j p i m p x x f p i i j i j i 2 ) ( dan 1 , , 2 11 , 2 7 ; 2 2 1 ) 1 ( 2 2 , , 2 9 , 2 5 ; ) 2 5 ( 2 ) 1 ( ) ( 2 2 3 ; 2 2 1 , , 4 , 2 ; 2 2 1 ) 1 ( 2 2 1 , , 3 , 1 ; 1 2 1 3 ) ( 2 ) ( , 1 , 1 , ,                                                        untuk p genap ip x x f p j j i p p j j i p p j j i m p x x f p i i j i j i 2 ) ( dan 1 ; 2 ) 1 ( 2 2 , 4 , 2 ; 2 ) 1 ( 2 3 , , 3 , 1 ; 2 ) ( 2 ) ( , 1 , 1 , ,      
               
dengan 1, 2, , i m   dan x i , j x i , j +1 merupakan edge yang  menghubungkan vertex ke- j dan vertex ke-( j +1) dari graph ke- i serta x i ,1 x i , p merupakan edge yang menghubungkan vertex ke-1  dan vertex ke- p dari graph ke- i .
Dari  pelabelan  di  atas,  diperoleh semua label vertex berupa bilangan ganjil dan  semua  label edge berupa  bilangan genap.  Jumlah  semua  label vertex
2 1 ) ( ) 1 2 ( mp i S mp i v     
dan jumlah semua label edge
) 1 ( 2 1      mp mp i S mp i e .    Karena   bobot
tiap vertex dari multicycle    graph ( m C p )    adalah w ( x )  = f ( x )  + f ( xy )  + f ( xz ) dengan y dan z merupakan vertex-vertex yang adjacent dengan x ,  diperoleh bobot vertex semuanya bilangan ganjil.
Untuk d =  2,  Persamaan  (3.1)
menjadi 3 2 1 2 3 2 ) 2 ) 1 ( ( ) ( ) 1 ( ) 1 2 (            
mp a mp a mp mp mp a mp mp mp mp mp
Jadi  terbukti  bahwa  pada multicycle ( m C p ) terdapat  (2 mp +  3,  2) VATL untuk
1  m dan 3  p . □
Sebagai  ilustrasi  dari  Teorema  3
diberikan contoh pelabelan untuk
beberapa multicycle .  Pada  Gambar  4 merupakan contoh pelabelan (27, 2) VATL untuk 3C 4 .

## SIMPULAN
Dari  pembahasan  di  atas  dapat disimpulkan  bahwa  pada multicycle graph ( m C p  ,  yakni  gabungan  beberapa cycle graph yang identik (a,d) VATL .
a. Setiap multicycle graph ( m C p ) mempunyai  ( a , d ) vertex  antimagic total  labeling dengan 6  a dan 6  d untuk semua 1  m dan 3  p . b. Pada multicycle ( m C p ) terdapat (2 mp + 2, 1) VATL untuk 1  m dan 3  p . c. Pada multicycle  graph ( m C p )  juga mempunyai  (2 mp +  3,  2) VATL untuk 1  m dan 3  p .
Dalam artikel ini telah dibahas keberlakuan  ( a,d ) VATL pada multicycle graph ( m C p )  untuk d =  1  dan d =  2.
Pembaca dapat meneliti untuk nilai d lain
yang  berlaku  atau  keberlakuannya  pada gabungan graph yang lain.
1 7 5 3 2 8 22 9 15 13 11 10 12 16 14 17 23 21 19 18 20 24 6 4
Gambar 4  (27, 2) VATL pada 3C 4 .

## 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.