Jurnal Ilmiah Matematika dan Pendidikan Matematika (JMP) Vol. 12 No. 1, Juni 2020, hal. 47-57 ISSN (Cetak) : 2085-1456; ISSN ( Online ) : 2550-0422

## PELABELAN ANTI AJAIB JARAK PADA SUATU GRAF PETERSEN DIPERUMUM
Dian Eka Wijayanti
Prodi Matematika, FAST, Universitas Ahmad Dahlan, Yogyakarta dian@math.uad.ac.id

## Aris Thobirin
Prodi Matematika, FAST, Universitas Ahmad Dahlan, Yogyakarta
ABSTRACT. One type of graph labeling is distance labeling which is labelled a graph based  on  the  distance  between  the  vertices.  This  distance  labeling  is  called  distance magic  labeling  (magic  labeling  distance)  if  each  vertex  has  the  same  distance  labeling weights.  The  distance  labeling  is  called  distance  antimagic  labeling  if  each  vertex  has different  distance  labeling  weights,  formed  an  arithmetic  progressive    a,  a+d,  a+2d,  ... ,a+(n-1)d , where d  >  0    .  This  paper  discusses  the  anti-magic  labeling  distance  on generalized  Petersen  graph,  denote  G  =  P  (n,  m)  with  n ≥ 3,  1 ≤ m  <n  /  2,  a  regular graph with degree 3 that has 2n vertices and 3n edges. More over, this paper also discuss about (a, d)-distance anti-magic labeling on generalized  Petersen graph.
Keywords : generalized  Petersen graph, distance labeling, distance antimagic labeling
ABSTRAK. Salah  satu  jenis  pelabelan  pada  graf  adalah  pelabelan  jarak  yang merupakan  pelabelan  graf  berdasarkan  jarak  antara  titik-titiknya.  Pelabelan  jarak  ini disebut distance magic labeling (pelabelan ajaib jarak) jika setiap titik mempunyai bobot pelabelan jarak  yang sama. Pelabelan jarak ini disebut (a, d) - distance antimagic labeling (pelabelan ( a,d )-anti ajaib jarak) jika setiap titik  mempunyai bobot pelabelan jarak yang berbeda,  membentuk suatu deret aritmatika progresif a, a+d, a+2d, ... ,a+(n-1)d , dengan nilai d > 0 .  Tulisan ini membahas tentang pelabelan  anti ajaib jarak pada graf petersen diperumum yaitu G= P(n, m) dengan n ≥ 3, 1 ≤ m <n/2 suatu  graf teratur berderajat 3 yang  mempunyai 2n titik    dan  3n  sisi.  Lebih lanjut, tulisan  ini juga  membahas  tentang pelabelan ( a,d )-anti ajaib jarak pada suatu graf petersen diperumum.
Kata Kunci : graf petersen diperumum, pelabelan jarak, pelabelan anti ajaib jarak

## 1. PENDAHULUAN
Secara  umum,  pelabelan  graf  dapat  didefinisikan  berdasarkan  distance (jarak)  antara  titik-titiknya.  Domain  dari distance  labeling (pelabelan  jarak) adalah himpunan semua titik v di G dan   kodomainnya adalah { 1, 2, ..., p } dengan p adalah  banyaknya  titik    pada  graf G .  Griggs  pada  tahun  1992  mendefinisikan suatu pelabelan jarak Ld ( 2,1 ) sebagai suatu label titik-titik berjarak 1 dan 2 yang harus  berbeda.  Konsep  pelabelan  jarak  dikemukakan  kembali  oleh  Miller    pada
tahun  2003  dengan  nama 1 - vertex  labeling yang  mendefinisikan  bobot  setiap titik x dalam graf G sebagai jumlah label dari  titik-titik yang memiliki jarak 1 dari x atau dengan kata lain bertetangga dengan x . Lebih lanjut, jika semua titik di G mempunyai bobot yang sama, katakan c ,  maka pelabelan ini dinamakan 1 - vertex- magic  vertex  labeling dan  konstanta c dinamakan  sebagai magic  konstan .  Pada tahun  2008,  Beena  membahas  tentang  Σ- labeling yang  sebenarnya  adalah 1- vertex-magic vertex labeling dan Σ’- labeling yang merupakan {0,1}-vertex- magic vertex labeling . Oneal   pada tahun 2013 menunjukkan bahwa magic konstan ini unik untuk setiap pelabelan jarak pada graf.
Suatu  pelabelan  jarak  dikatakan  pelabelan  ( a,d )-anti  ajaib  jarak  jika himpunan dari bobot tiap titiknya membentuk himpunan aritmatika yang progresif { a,  a+d,  a+2d,  ...,  a+(n-1)d }.  Graf  yang  mempunyai    pelabelan  ( a,d )-anti  ajaib jarak  dinamakan  graf  ( a,d )-anti  ajaib  jarak.  Arumugam  (2012)  menyajikan beberapa hasil pelabelan ( a,d )-anti ajaib jarak ini dalam penelitiannya pada tahun 2012.  Dia  juga  membuktikan  bahwa disjoint  copies dari hypercube Q3 adalah graf    ( a,1 )-  anti  ajaib  jarak.  Simanjuntak  (2013)  kemudian  menyelidiki  beberapa syarat  perlu  bagi  keberadaan  graf  anti  ajaib  jarak- D yaitu  untuk  suatu  graf terhubung  yang  memuat  satu  atau  lebih cycle ,  graf  matahari,  graf  prisma,  graf lengkap,  graf roda, graf kipas dan graf persahabatan. Tulisan  ini bertujuan untuk mengkaji tentang pelabelan jarak anti ajaib  pada suatu graf Petersen diperumum. Hal ini dilakukan dengan menentukan nilai a yang merupakan konstanta anti ajaib dari  suatu  graf  kemudian  menyelidiki  eksistensi  himpunan  bobot  titik  { a,a+d, a+2d,...,a+(n-1)d }.  Lebih  lanjut  menentukan  pola  pelabelan  titik-titik  yang menghasilkan himpunan bobot titik { a,a+d,a+2d,...,a+(n-1)d } guna merumuskan fungsi pelabelan jaraknya.

## 2. HASIL DAN PEMBAHASAN
2.1 Pelabelan Jarak
Suatu  pelabelan  berdasarkan  jarak  (pelabelan  jarak) dikatakan  pelabelan jarak  anti  ajaib  jika  bobot  setiap  titiknya  berbeda.  Pelabelan  jarak  anti  ajaib tersebut  adalah  pelabelan  jarak (a,d) -anti  ajaib  jika  himpunan  dari  bobot  dari
Pelabelan Anti Ajaib Jarak                                                                                                 49
setiap  titiknya  membentuk  himpunan  aritmatika  yang  progresif    { a,a+d,a+2d,..., a+(n-1)d }. Graf yang mempunyai pelabelan (a,d) anti ajaib jarak dinamakan graf anti  ajaib  jarak. Arumugam  (2012),    menyajikan  beberapa  hasil  pelabelan (a,d)- anti ajaib jarak ini dalam penelitiannya.
Definisi 1 (Shafiq, dkk., 2009)
Suatu pelabelan ajaib jarak- D ( D - distance magic labeling ) pada graf G(V,E) yang mempunyai orde p dan ukuran q adalah suatu fungsi bijektif f : V → {1,2,..., p} dimana terdapat suatu konstanta k sehingga untuk setiap titik berlaku ( )   ∑ ( ) ( ) (1)
N(x) adalah himpunan titik-titik  yang berjarak D dari x .   Konstanta k dinamakan konstanta ajaib dan w(x) merupakan bobot titik x .
Definisi 2 (Simanjuntak, dkk., 2013)
Suatu  pelabelan (a,d) -anti  ajaib  jarak- D (( a,d )- D - distance  antimagic  labeling ) pada graf G(V, E) yang   mempunyai order p dan size q ,  adalah  suatu  fungsi bijektif f : V → {1, 2,..., p} dengan setiap titik memiliki bobot w(x) yang berbeda  dan  himpunan  dari  bobot  tersebut  dapat  dinyatakan  sebagai  { a,  a+d, a+2d,..., a+(p-1)d }.
Beberapa  syarat  perlu  bagi  suatu  graf  agar  memiliki  pelabelan (a,d) -anti  ajaib jarak- D dapat dilihat pada lemma-lemma berikut (Arumugam, dkk., 2012),

## Lemma  3
Suatu graf yang memuat dua titik dengan D -tetangga yang sama bukan merupakan graf anti ajaib jarak- D.

## Lemma  4
Misalkan G suatu  graf teratur- r . Jika G adalah  graf (a,d) -anti ajaib jarak maka
(     )    (     ) ( )

## Akibat  5
Diketahui G suatu  graf teratur- 3 dengan order p dan size q .  Jika G adalah graf ( a, d )-anti ajaib jarak maka a = p+ 2 dan d = 1 .

## 2.2 Pelabelan Anti Ajaib Jarak pada Graf Petersen Diperumum
Suatu Graf G(V, E) dengan order p dan ukuran q dinamakan Graf Petersen diperumum  ( generalized Petersen graph ) dinotasikan P(n,m) ,
jika G merupakan  graf  kubik  dengan p  =  2n dan q  =  3n .  Himpunan  titik,
*
+ dan  himpunan  sisi, {* +  * +  * +}
*           + .  Jika  nilai  indeks i+1 maupun  indeks i+m lebih  besar  dari n maka nilai tersebut akan dimodulokan dengan n (Ngurah, dkk., 2003).
Pelabelan  anti  ajaib  jarak  pada  graf  petersen  diperumum  akan  disajikan dalam  bentuk  lemma  berikut  beserta  bukti  dan  proses  pembuktiannya.  Pelabelan jarak yang dimaksud disini adalah pelabelan jarak- 1 yang selanjutnya akan ditulis sebagai  pelabelan  jarak  saja.  Bobot  jarak  yang  dimaksud  pada  penelitian  ini adalah  bobot      jarak- 1 yang  selanjutnya    akan  ditulis  sebagai  bobot  jarak  saja. Untuk  menentukan  pola  pelabelan  pada  graf  Petersen P(n,1) ,  akan  diselidiki pelabelan pada graf Petersen diperumum P(3,1), P(4,1), P(5,1) dan P(6,1) .
Pada graf petersen P(3,1) dengan jumlah  titik p = 6 dan jumlah sisi q =
9 , didefinisikan pelabelan f sebagai berikut
f(u 1 ) = 1 f(u 2 ) = 2 f(u 3 ) = 3 f(v 1 ) = 4 f(v 2 ) = 6 f(v 3 ) = 5
diperoleh  himpunan  bobot  dari  titik-titik P(3,1) adalah  {8,  9,  10,  11,  12,13  } dengan a = 8 dan d = 1 sehingga dapat dinyatakan bahwa P(3, 1) merupakan graf (8,1)-anti ajaib jarak.   Graf Petersen P(4,1) yang mempunyai jumlah titik yaitu p = 8 dan jumlah sisi q = 12 dengan pendefinisian  pelabelan f sebagai berikut f(u 1 ) = 1 f(u 2 ) = 2 f(u 3 ) = 3 f(v 1 ) = 5 f(v 2 ) = 8 f(v 3 ) = 7
Pelabelan Anti Ajaib Jarak                                                                                                 51
f(u 4 ) = 4 f(v 4 ) = 6 diperoleh  himpunan  bobot  dari  titik-titik P(4,1) adalah  graf  (12,1)-anti  ajaib dengan fungsi pelabelan f yang didefinisikan sebagai
f(u 1 ) = 1 f(u 2 ) = 2 f(u 3 ) = 3 f(u 4 ) = 4 f(u 5 ) = 5 f(v 1 ) = 6 f(v 2 ) = 10 f(v 3 ) = 9 f(v 4 ) = 8 f(v 5 ) = 7
Graf petersen P(6,1) adalah graf (14,1)-anti ajaib jarak.dengan fungsi pelabelan f sebagai berikut
f(u 1 ) = 1 f(u 2 ) = 2 f(u 3 ) = 3 f(u 4 ) = 4 f(u 5 ) = 5 f(u 6 ) = 6 f(v 1 ) = 7 f(v 2 ) = 12 f(v 3 ) = 11 f(v 4 ) = 10 f(v 5 ) = 9 f(v 6 ) = 8
Untuk lebih jelas, pada Gambar 1 dapat dilihat  pelabelan ( a, d )-anti ajaib jarak pada  graf Petersen P(6,1).
Gambar 1 . Pelabelan (14,1)-Anti Ajaib Jarak pada  Graf Petersen
Bobot titik-titik pada P(6,1) adalah
w(u 1 ) = 15 w(u 2 ) = 16 w(v 1 ) = 21 w(v 2 ) = 20
f(u 5 ) = 5 f(u 4 ) = 4 f(u 3 ) = 3 f(u 2 ) = 2 f(u 1 ) = 1 f(u 6 ) = 6 f(v 5 ) = 9 f(v 6 ) = 8 f(v 1 ) = 7 f(v 4 ) = 10 f(v 3 ) = 11 f(v 2 ) = 12
w(u 3 ) = 17 w(u 4 ) = 18 w(u 5 ) = 19 w(u 6 ) = 14 w(v 3 ) = 25 w(v 4 ) = 24 w(v 5 ) = 23 w(v 6 ) = 22
Himpunan bobot  dari titik-titik P(6,1) adalah {14, 15, 16, 17, 18, 19, 20, 21,  22,  23,  24,  25  }  yang  dapat  dinyatakan  sebagai    barisan  { a,  a+d,  a+2d,..., a+(p-1)d }  dengan a  =  14 dan d  =  1 sehingga  dapat  dinyatakan  bahwa P(6,  1) merupakan graf (14,1)-anti ajaib jarak.
Pelabelan  anti  ajaib  pada  graf  Petersen P(n,1) yang  mempunyai  jumlah titik  yaitu p  =  2n dan  jumlah  sisi q  =  3n akan  dijelaskan  melalui  lemma  dan akibat berikut.

## Lemma 6
Graf petersen diperumum G(V, E) = P(n,1) mempunyai pelabelan (2n+2, 1)-anti ajaib jarak
Bukti. G(V,E) adalah graf petersen  diperumum P(n,1) maka V = { u 1 , u 2 , ... , u n v 1 , v 2 , ... , v n } dan , {* +  * +  * +} *           + .
Pada Tabel  1, dapat  dilihat bahwa setiap titik mempunyai  3 titik  yang berjarak 1 (bertetangga) dengannya.
Tabel 1 . Ketetanggaan Titik-titik pada Graf Petersen P(n, 1) Titik Titik tetangga 1 Titik tetangga 2 Titik tetangga 3 u 1 u n u 2 v 1 u 2 u 1 u 3 v 2 u n u n-1 u 1 v n v 1 v n v 2 u 1 v 2 v 1 v 3 u 2 v n v n-1 v 1 u n
Maka bobot setiap titik adalah
( )    ( )    ( )    ( ) ( )    ( )    ( )    ( )
( )    ( )    ( )    ( )
( )    ( )    ( )    ( ) ( )    ( )    ( )    ( )
( )    ( )    ( )    ( )
Total bobot setiap titik pada G adalah
∑  ( ) ∑  ( ) ∑  ( ) ∑  ( ) ∑  ( ) ∑  ( )
( (    (     )   ))   ( (         (     )   ))
(      )
∑  ( ) ∑  ( ) ∑  ( ) ∑  ( ) ∑  ( ) ∑  ( )
( (    (     )   ))   ( (         (     )   ))
(      )
∑  ( ) ∑  ( )
(              )

## ( (      )   (     )   )
Yang merupakan  deret aritmatika dengan suku pertama 2n+2 dan beda 1.

## Akibat 7
Jika P(n,  1) mempunyai    pelabelan  (2n+2,1)-anti  ajaib  jarak  maka  pelabelan tersebut dapat didefinisikan sebagai berikut :
( )                                                      *           +
( )   { (      )                           *        +
Bukti.
Pilih pelabelan f, suatu fungsi bijektif dengan ketentuan sebagai berikut
( )                                                    *           + ( ) { * +
Gambar 2 . Pelabelan (a, d)-Anti Ajaib Jarak Pada P(n, 1)
Diperoleh barisan  bobot setiap titik adalah
( )         ( )    ( )    ( )
( )         ( )    ( )    ( ) ( )         ( )    ( )    ( )
( )    ( )    ( )    ( ) ( )          ( )    ( )    ( ) ( )          ( )    ( )    ( ) ( )          ( )    ( )    ( ) ( )    ( )    ( )    ( )
( )    ( )    ( )    ( ) ( )    ( )    ( )    ( ) ( )    ( )    ( )    ( )
Sesuai  dengan    Lemma.  6,    bobot  titik-titik  pada P(n,  1) dirumuskan  sebagai berikut,
( )   { *               +
( )   { *           + *    +
dengan
∑  ( ) ∑  ( ) ( (      )   (     )   )
Sebagai penutup dari paper ini, disampaikan sebuah konjektur sebagai bahan penelitian lebih lanjut.

## Konjektur 8
Setiap graf petersen diperumum P(n, m) mempunyai pelabelan ( a, d )-anti ajaib jarak untuk nilai n dan m tertentu.

## 3. KESIMPULAN DAN SARAN
Dari  pembahasan  diatas,  dapat  disimpulkan  bahwa  graf  Petersen diperumum P(n,1) yang merupakan suatu graf teratur berderajat 3 dengan jumlah titik 2n , jumlah sisi 2n merupakan graf anti ajaib jarak dan  mempunyai pelabelan ( 2n+2,1 )-anti  ajaib  jarak.  Walaupun  baru  berdasarkan  dugaan  ( counting argument ),  graf  Petersen  diperumum P(n,2) juga  merupakan  ( 2n+2,1 )-anti  ajaib jarak dan diharapkan dapat memjadi bahan untuk penelitian lebih lanjut.

## DAFTAR PUSTAKA
Arumugam, S., Froncek, D., Kamatchi, N., Distance Magic Graphs-A Survey , J.
Indones. Math. Soc. Special Edition (2011),  11-26.
Arumugam, S., Kamatchi, N., On (a;d)-Distance Antimagic Graphs , Australasian J. Combinat. 54 (2012), 279-287.
Beena, S., On Σ and Σ’ Labelled Graphs , Discrete Math., 309 (2009), 1783-1787. Griggs,  R.  Yeh,  K.,  Labelling  Graphs  with  a  Condition  at  Distance  2, Siam  J. Discrete Math. 4 (1992), 586 – 595.
Kovar,  P.,  Froncek,  D.,  Kovarova,  T., A  Note  on  4-Regular  Distance  Magic Graphs , Australasian J. Combinat. 54 (2012),  127-132. Miller, M., Simanjuntak,  R., Distance  Magic Labelings of  Graphs , Australasian J. Combinat. 28 (2003), 305 – 315.
Ngurah,  A.A.G.,  Baskoro,  E.T., On  Magic  and  Antimagic  Total  Labeling  of Generalized Petersen Graph . Utilitas Math. 63 (2003), 97-107.
O’neal, A., Slater , P. J., Uniqueness Of Vertex Magic Constants , Siam J. Discrete Math., 27 (2) (2013), No. 2,  708–716, 2013.
Shafiq,  M.K.,  Ali,  G.,  Simanjuntak,  R., Distance  Magic  Labeling  of  a  Union Graphs , AKCE J. Graphs Combinat. 6 (1) (2009), 191-200.
Simanjuntak, R., Elviyenti, M., Jauhari, M. N., Praja, A.S., Purwasih, I.A., Magic Labelings  of  Distance  at  Most  2 , 37th  Australasian  Conference  on Combinatorial
Mathematics and Combinatorial Computing, arXiv:1312.7633 [math.CO], 2013.
Simanjuntak,  R.,  Wijaya,  K., On  Distance  Antimagic  Graphs , ArXiv  1312 [Math.CO] 28 Dec.2013, 2013.