PADA GRAF PRISMA BERCABANG

PELABELAN TOTAL SUPER (𝒂, 𝒅)-BUSUR ANTI AJAIB PADA GRAF PRISMA BERCABANG

Achmad Fahrurozi1,2, Dewi Putrie Lestari1,2, Iffatul Mardhiyah1,2 1

2

Universitas Gunadarma Depok Program Magister Fakultas MIPA Universitas Indonesia Depok

Email : (achmad.fahrurozi,dewi.putrie, iffatul.mardhiyah)@ui.ac.id

ABSTRAK Misalkan G adalah graf dengan himpunan simpul V=V(G) dan himpunan busur E=E(G) . Pelabelan total (𝑎, 𝑑)-busur anti ajaib merupakan suatu pemetaan bijektif 𝜆 dari 𝑉 ∪ 𝐸 ke himpunan bilangan bulat 1,2, … , 𝑛 + 𝑒 dengan 𝑛 = 𝑉 dan 𝑒 = 𝐸 menyatakan banyak simpul dan busur pada G dan himpunan dari bobot semua busur 𝑥𝑦𝜖𝐸 , 𝑤 𝑥𝑦 = 𝜆 𝑥 + 𝜆 𝑥𝑦 + 𝜆(𝑦) , adalah 𝑎, 𝑎 + 𝑑, 𝑎 + 2𝑑, … . + 𝑒 − 1 𝑑 (𝑎 > 0 dan 𝑑 ≥ 0 , 𝑎 dan 𝑑 adalah bilangan bulat). Oleh karena itu, himpunan dari bobot semua busur pada G membentuk barisan aritmetika dengan suku awal 𝑎 dan 𝑑 . Selanjutnya, pelabelan total (𝑎, 𝑑)-busur anti ajaib dikatakan pelabelan total super(𝑎, 𝑑)-busur anti ajaib jika 𝜆 𝑉 = 1,2, … . , 𝑛 dan 𝜆 𝐸 = 𝑛 + 1, 𝑛 + 2, … . , 𝑛 + 𝑒 . Dalam makalah ini akan diberikan konstruksi pelabelan total super(𝑎, 𝑑)-busur anti ajaib, pada graf prisma bercabang yang merupakan gabungan dari graf prisma yang diperumum dengan graf bintang. Kata kunci : pelabelan total (𝑎, 𝑑)-busur anti ajaib, pelabelan total super (𝑎, 𝑑)-busur anti ajaib, graf prisma yang diperumum, graf bintang.

PENDAHULUAN Pada makalah ini, graf yang digunakan adalah graf berhingga, sederhana, dan tak berarah. Misalkan G adalah graf dengan himpunan simpul V=V(G) dan himpunan busur E=E(G), dimana 𝑛 = 𝑉 dan 𝑒 = 𝐸 menyatakan banyak simpul dan busur pada G. Sejak definisi pelabelan total (𝑎, 𝑑)-busur anti ajaib diperkenalkan oleh Simanjuntak, Bertault dan Miller [2] pada tahun 2000, konstruksi pelabelan total (𝑎, 𝑑)-busur anti ajaib untuk graf terhubung terus mengalami perkembangan. Hal ini mendorong munculnya banyak penemuan konstruksi pelabelan total (𝑎, 𝑑)-busur anti ajaib khususnya yang memuat graf prisma yang diperumum. Berdasarkan [3] , secara matematis pelabelan total (𝒂, 𝒅)-busur anti ajaib dari graf G didefinisikan sebagai suatu pemetaan bijektif 𝜆 dari 𝑉 ∪ 𝐸 ke himpunan bilangan bulat 1,2, … , 𝑛 + 𝑒 sedemikian sehingga himpunan bobot busur 𝑤 𝑥𝑦 = 𝜆 𝑥 + 𝜆 𝑥𝑦 + 𝜆 𝑦 , 𝑥𝑦 ∈ 𝐸 , membentuk barisan aritmatika 𝑎, 𝑎 + 𝑑, 𝑎 + 2𝑑, … . , 𝑎 + 𝑒 − 1 𝑑, dengan suku awal 𝑎 > 0 dan beda 𝑑 ≥ 0. Jika nilai 𝑑 = 0 maka pelabelan 𝜆 disebut pelabelan total busur ajaib. Suatu pelabelan total (𝒂, 𝒅)-busur anti ajaib dikatakan super (𝒂, 𝒅)-busur anti ajaib jika himpunan simpul diberi label 1,2,3, … , 𝑛 . Selanjutnya akan diberikan penjelasan mengenai definisi EAV yang akan digunakan dalam pembahasan ini. Pelabelan 𝑎, 𝑑 -EAV (simpul busur anti ajaib) pada graf G 𝑛, 𝑒 adalah pemetaan injektif 𝑓: 𝑉 𝐺 → 1,2,3, … , 𝑛 sedemikian sehingga himpunan bobot busur dari semua busur di graf G, 𝑓 𝑢 + 𝑓 𝑣 : 𝑢𝑣 ∈ 𝐸(𝐺) = 𝑎, 𝑎 + 𝑑, 𝑎 + 2𝑑, … , 𝑎 + 𝑒 − 1 𝑑 . Dalam makalah ini akan dibahas mengenai pelabelan total super (𝑎, 𝑑)-busur anti ajaib pada suatu graf sederhana baru yang dinamakan graf prisma bercabang.

GRAF PRISMA BERCABANG Graf prisma bercabang merupakan pengembangan dari graf prisma yang diperumum. Graf prisma bercabang diperoleh dengan cara menambahkan graf bintang pada setiap ujung simpul pada graf prisma yang diperumum Cn  Pk dengan 𝑛 simpul ganjil, sehingga titik pusat graf bintang tersebut berhimpit dengan simpul pada graf prisma yang diperumum pada lapisan terluar. Graf prisma bercabang dengan graf prisma yang diperumum yang mempunyai n simpul ganjil serta banyak simpul pada graf path sebanyak 𝑘 dan banyak simpul graf bintang adalah m dinotasikan dengan Cn  Pk  Sm

PENAMAAN GRAF PRISMA BERCABANG Contoh : Graf C3  P1  Sm

e23

e13

12 1

3 em

e

v11

e12

e12

e11 3 e3m

e312

e23m  2

e31 e32

e23m 1

e22

e12 2

3 em 1

3 2m

e

3 em 2

Gambar 1. Contoh Penamaan Graf Prisma Bercabang C3  P1  Sm

Berikut akan dibahas mengenai batasan untuk beda (d) barisan dari bobot busur. Dengan pelabelan pada gambar 1 akan diperoleh :

a  1   k  1 n  mn  1  2  4   k  1 n  mn dan suku terakhir dari barisan bobot busur tersebut adalah

a   e  1 d   4   k  1 n  mn     2k  1 n  mn  1 d Berikutnya kita akan mencari batasan untuk d : Karena pelabelan busur terbesar adalah

E  V   2k  1 n  mn   k  1 n  mn   3k  2  n  2mn

..... i 

Bobot maksimum yang mungkin diperoleh adalah

 k  1 n  mn  3k  2 n  2mn   k  1 n  mn 1  5k  4 n  4mn 1

....  ii 

Sehingga dari (i) dan (ii) haruslah terpenuhi

 4   k  1 n  mn     2k  1 n  mn  1 d  5k  4  n  4mn  1   2k  1 n  mn  1 d   4k  3 n  3mn  5 d

4kn  3mn  3n  5 6kn  3mn  3n  3   2kn  mn  n  1  2kn  mn  n  1

Berdasarkan sifat transitif, maka diperoleh

d 3 Jadi, nilai d yang mungkin adalah d=0, d=1, d=2.

PELABELAN TOTAL 𝒂, 𝒅 -BUSUR ANTI AJAIB PADA GRAF PRISMA BERCABANG a. Konstruksi pelabelan super (𝑎, 2)-busur anti ajaib pada graf prisma bercabang

Definisikan pelabelan simpul sebagai berikut :

 i 1 ; i ganjil   2 1   vi     n  i  1 ; i genap  2  n 1 j 1 ; j  i  p mod n , p  ganjil  1, p  n    vi   2   vij    n 1    vij 1    n ; lainnya  2 dengan j  2,..., k  1

n 1  k 1   vi   2  cn ; j  i  g mod n, g  n,  untuk suatu g bilangan ganjil positif  jc   vi      n 1   vik 1     c  1 n ; Lainnya   2 dengan j  k  2 Definisikan pelabelan busur sebagai berikut :

  ei1    k  1 n  nm  i ; i  1, 2,..., n n 1  j 1 ei  2n  ; j  i  1mod n   2 j   ei     e j 1  n  n  1 ; lainnya  i 2 n 1  j 1 j ei  2n  ; j  i  1mod n   2   eij j 1     e j 1 j  n  n  1 ; lainnya  i 2 dengan j  2,..., k  2

Berikut ini diberikan contoh pelabelan total super (𝑎, 2)-busur anti ajaib pada graf C3  P1  S2

7

10

22

25 5 16

21

1

19

13

14 3

2 11

18

27

6 24

15

17

4

23

9

20 26

8

12

Gambar 2. Pelabelan Super (a,d)-busur anti ajaib pada graf prisma bercabang C3  P1  S2

b. Pada graf prisma bercabang dengan total simpul sebanyak ganjil, pelabelan total super (𝑎, 𝑑)-busur anti ajaib dengan d=1 belum dapat ditentukan dapat dibentuk atau tidak. Namun kami membuktikan bahwa tidak mungkin membentuk barisan aritmetika untuk EAV dengan beda 2. Bukti bahwa EAV tidak dapat membentuk barisan aritmetika dengan beda 2 Diketahui : EAV terkecil yang mungkin = 3 Jumlah busur

=

Jumlah simpul

=

 2k  1 n  mn  k  1 n  mn

Sehingga jika ingin membuat EAV yang membentuk barisan aritmetika dengan beda 2 maka barisan EAV yang terbentuk 3,5,7,,U r  dimana U r menyatakan suku terakhir untuk barisan EAV. Karena EAV merupakan barisan aritmetika maka U r dapat ditulis  3  (r  1)2  karena jumlah busur

 2k  1 n  mn maka : U r   3  ( 2k  1 n  mn  1)2    3   4k  2  n  2mn  2    4k  2  n  2mn  1

maksimum adalah

..... 1

Label simpul paling besar

 k  1 n  mn

dijumlahkan dengan label simpul sebelumnya

 k  1 n  mn  1 maka akan diperoleh jumlah EAV maksimum yaitu : Jumlah EAV max   k  1 n  mn   k  1 n  mn  1   2k  2  n  2mn  1 ..... 2 Untuk n  3 maka dari persamaan (1) dan (2) diperoleh

 4k  2 n  2mn  1



 2k  2 n  2mn 1

Oleh karena itu, untuk membentuk EAV menjadi barisan aritmetika dengan beda 2 tidak dapat dilakukan karena hal itu tidak sesuai dengan jumlah simpul dan busurnya. Dapat disimpulkan bahwa tidak mungkin terdapat EAV yang membentuk barisan aritmetika dengan beda 2.

KESIMPULAN Dalam makalah ini telah dibuktikan bahwa pelabelan total super (𝑎, 𝑑)-busur anti ajaib pada graf prisma bercabang memiliki batasan d<3. Telah ditentukan pelabelan total super (𝑎, 2)-busur anti ajaib dan telah dibuktikan bahwa untuk graf prisma bercabang dengan total simpul sebanyak ganjil tidak dapat dibentuk pelabelan total super (𝑎, 1) -busur anti ajaib pada graf prisma bercabang Cn  Pk  Sm , yang merupakan gabungan antara graf prisma yang diperumum dan graf bintang. Untuk pembahasan lebih lanjut dapat dicari konstruksi pelabelan total super (𝑎, 𝑑)-busur anti ajaib dari graf prisma bercabang Cn  Pk  Sm untuk kasus = 0 , dengan cara mengubah label untuk busur dari yang terbesar ke yang terkecil.

PENUTUP Kami ucapkan terimakasih kepada ibu Kiki A. Sugeng selaku dosen pembimbing.

DAFTAR PUSTAKA [1] Widya M. Niagara, Denny R Silaban, dan Kiki A. Sugeng, pelabelan total (𝑎, 𝑑)-busur anti ajaib pada gabungan graf prisma yang diperumum,Pros seminar nasional matematika(2010). [2] R. Simanjuntak, F. Bertault dan M.Miller, Two new (𝑎, 𝑑)-antimagic graph labeling, Proc. Of Eleventh Australian Workshop of Combinatorial Algoritm (2000),179-189. [3] J. Gallian, A dynamic survey of graph labeling, The electronic journal of Combinatorics,16 (2009), #DS6. [4] M. Bača dan M. Miller, Super Edge-Antimagic Graphs: A Wealth of Problems and Some Solutions, Brown Walker Press, Boca Raton-Florida, 2008.