J. Math. and Its Appl. ISSN: 1829-605X Vol. 3, No. 2, Nov 2006, 49–56

## Batas Bilangan Ajaib Pada Graph Caterpillar

## Chairul Imron
Jurusan Matematika FMIPA ITS Surabaya imron-its@matematika.its.ac.id

## Abstrak
Jika suatu graph diberi label pada setiap simpul dan sisi dengan bilangan sebanyak simpul dan sisi, maka graph tersebut mempunyai sifat total sisi ajaib jika label pada setiap sisi dan simpul yang insiden dengan sisi tersebut dijumlahkan mempunyai jumlah yang sama. Bilangan tersebut dinamakan bilangan ajaib dari suatu graph. Untuk mendapatkan bilangan tersebut perlu dilakukan terlebih dahulu mencari batas minimum dan maksimum. Pada paper ini akan dicari batas minimum dan maksimum bilangan ajaib dari graph caterpillar.
Kata Kunci: Graph Caterpillar, Total Sisi Ajaib

## 1. Pendahuluan
Pemberian label pada graph G adalah pemetaan satu-satu yaitu memetakan semua simpul dan sisi dari graph tersebut ke suatu bilangan yang biasanya merupakan bilangan 1 , 2 , 3 , · · · . Dengan kata lain, pelabelan graph adalah pemberian label pada simpul-simpul dan sisi-sisi dari graph, sehingga setiap simpul dan setiap sisi mempunyai label yang berbeda. Pelabelan yang domainnya berupa himpunan sim- pul, himpunan sisi, atau keduanya yang biasanya disebut dengan pelabelan simpul, pelabelan sisi , dan pelabelan total [3]. Pada paper ini, akan dibahas pelabelan total, khususnya pelabelan total sisi ajaib yakni pelabelan dimana jumlah label sisi dan
label simpul-simpul yang menempel pada sisi tersebut selalu sama untuk setiap sisi. Jumlah tersebut disebut angka ajaib , yang biasa dilambangkan dengan hu- ruf k . Ide pelabelan ini dikenalkan pertama kali oleh Sedl´ a ˇ c ek [5] pada 1960-an, selanjutnya diformulasikan oleh Kotzig dan Rosa [6] pada tahun 1970-an.
Pada paper ini akan dicari batas minimum dan maksimum himpunan kritis pada pelabelan suatu graph. Graph yang akan dikaji adalah graph caterpillar. Pelabelan pada sebuah graph diberi tanda dengan sejumlah label pada simpul dan sisi graph, sehingga setiap label sisi pada graph tersebut tergantung kepada label kedua simpul yang menempel pada sisi tersebut.
Pada paper ini, hanya membahas pelabelan total sisi ajaib yang didefinisikan sebagai berikut:
Definisi 1.1 [3, 7, 1, 2] Pelabelan total sisi ajaib pada graph G adalah pemetaan satu-satu λ dari V ∪ E kepada himpunan bilangan bulat { 1 , 2 , 3 , . . . , v + e } dengan v = | V | dan e = | E | , sedemikian sehingga ada suatu bilangan konstan k dimana
λ ( x ) + λ ( xy ) + λ ( y ) = k (1)
untuk setiap sisi xy ∈ E
Untuk lebih mudah, sebut λ ( x ) + λ ( xy ) + λ ( y ) sebagai penjumlahan sisi xy , dan k adalah angka ajaib dari graph G . Suatu graph disebut ajaib jika graph tersebut dapat dikenakan pelabelan total sisi ajaib.
Suatu graph mempunyai total sisi-ajaib, maka jumlah angka ajaib pada setiap sisinya adalah jumlahan yang memuat semua label pada simpul dan sisi ditambah dengan d i − 1 kali simpul yang mempunyai derajat d i atau
k | E | = 1 + 2 + 3 + . . . + ( v + e ) + Σ( d i − 1) x i (2)
Pada paper ini akan dikaji, bagaimana mencari batas minimal dan maksimal bilangan ajaib dari graph caterpillar C n .

## 2. Hasil
Pada bagian ini akan dibahas bagaimana mencari batas minimal dan maksimal bilangan ajaib dari graph caterpillar yang sesuai dengan Definisi 1.1 yang diny- ataka dalam dua teorema, yaitu Teorema 2.1 dan Teorema 2.2. Sebelum lebih jauh, perhatikan beberapa pengertian simbul sederhana dibawah ini:
1. S v menyatakan jumlah label pada semua simpul
2. S e menyatakan jumlah label pada semua sisi
3. p i jumlah simpul daun pada star ke i
4. d i jumlah simpul pusat star ke i
5. x i = λ ( v i 0 ) label pada pusat star ke i
Gambar 1: Graph Caterpillar
Perhatikan Gambar 1 adalah gambar graph caterpilar yang terdiri dari n graph star yang terhubung pada pusat graph star, oleh karena itu
V = { S 1 , S 2 , . . . , S n } dimana
S i = { v i 0 , v i 1 , v i 2 , . . . , v ip 1 }
dengan p i adalah banyaknya daun pada S i dan v i 0 adalah simpul pusat star ke i , dengan i = 1 , 2 , · · · , n , sehingga jumlah simpul pada graph caterpillar C n adalah jumlah semua daun pada setiap star ditambah dengan jumlah simpul pusat star atau
v = | V | = n X i =1 | S i | = n X i =1 ( p i + 1) = n + n X i =1 p i
karena graph caterpillar termasuk graph pohon, maka jumlah sisi pada graph caterpillar C n adalah e = | E | = v − 1 sehingga jumlah bilangan integer yang dibutuhkan untuk melabeli caterpillar adalah
v + e = 2( n + n X i =1 p i ) − 1
Teorema 2.1 Setiap graph caterpillar C n mempunyai batas minimum bilangan ajaib adalah
k ≥ 2(( n + P n i =1 p i ) − 1)( n + n X i =1 p i ) + n + 1 2 n X i =1 p i ( n + n X i =1 p i ) − 1
Bukti:
Pandang graph caterpillar C n diatas dan perhatikan definisi pelabelan total sisi ajaib, bahwa jumlah label pada setiap sisi dan simpul yang insiden dengan sisi tersebut harus mempunyai jumlah yang sama, sehingga setiap label pada simpul akan digunakan atau dijumlahkan pada sisi yang lain sesuai dengan derajat pada simpul tersebut.
Oleh karena itu
ke ≥ S v + S e + n X i =1 ( d i − 1) x i
karena d i − 1 = p i , maka
ke ≥ S v + S e + n X i =1 p i x i (3)
Label pada setiap simpul akan digunakan atau dijumlah sesuai besarnya der- ajat dari simpul tersebut, maka bilangan ajaib akan minimum jika semua simpul mempunyai label bilangan terkecil, khususnya pada label simpul pada pusat star. Label yang mungkin dikenakan pada simpul yaitu
λ ( simpul ) = 1 , 2 , 3 , . . . , v
Karena tidak diketahui derajat terbesar simpul pada star, maka kemungkinan pelabelan pada pusat star yaitu
n X i =1 p i x i = p 1 1 + p 2 2 + · · · + p n n, atau = p 1 n + p 2 ( n − 1) + · · · + p n 1 , atau = p 1 2 + p 2 4 + · · · + p n 2 n, atau yang lainya
Jika dianggap derajat dari simpul pusat adalah sama, dan label pada simpul di- ambil rata-rata, yaitu
1 + 2 + 3 + · · · + n n = n ( n + 1) n = n + 1 2
maka
n X i =1 p i x i = n + 1 2 n X i =1 p i (4)
Sedangkan
S v + S e = 1 + 2 + 3 + · · · + ( v + e ) = 1 + 2 + 3 + · · · + 2( n + n X i =1 p i ) − 1 = (2( n + n X i =1 p i ) − 1)(2( n + n X i =1 p i )) 2 = 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) (5)
Jika Persamaan (5) dan Persamaan (4) disubstitusikan ke Persamaan (3), men- jadi
ke ≥ 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) + n + 1 2 n X i =1 p i
atau bilangan ajaibnya adalah
k ≥ 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) + n + 1 2 n X i =1 p i ( n + n X i =1 p i ) − 1 ¥ (6)
Teorema yang kedua adalah batas maksimum yang mungkin pada caterpillar, yaitu
Teorema 2.2 Setiap graph caterpillar C n mempunyai batas maksimum bilangan ajaib adalah
k ≤ 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) + 1 2 Ã 3 n − 1 + 4 n X i =1 p i ! n X i =1 p i ( n + n X i =1 p i ) − 1
Bukti:
Dengan cara yang seperti teorema sebelumnya, maka
ke ≤ S v + S e + n X i =1 p i x i (7)
Label pada setiap simpul akan digunakan atau dijumlah sesuai besarnya dera- jat dari simpul tersebut, maka bilangan ajaib akan maksimum jika label pada sisi adalah label terkecil yaitu
λ ( sisi ) = 1 , 2 , 3 , . . . , ( v − 1)
atau
λ ( sisi ) = 1 , 2 , 3 , . . . , ( n + n X i =1 p i − 1)
atau label pada simpul adalah label terbesar, yaitu
λ ( simpul ) = ( n + n X i =1 p i ) , ( n + n X i =1 p i + 1) , . . . , 2( n + n X i =1 p i ) − 1
Karena tidak diketahui derajat terbesar simpul pada star, maka kemungkinan pelabelan pada pusat star yaitu
n X i =1 p i x i = p 1 ( n + n X i =1 p i ) + p 2 ( n + n X i =1 p i + 1) + · · · + p n (2( n + n X i =1 p i ) − 1) , atau = p 1 (2( n + n X i =1 p i ) − 1) + p 2 (2( n + n X i =1 p i ) − 2) + · · · + p n ( n + n X i =1 p i )
Jika dianggap derajat dari simpul pusat adalah sama, dan label pada simpul di- ambil rata-rata, yaitu
(2( n + n X i =1 p i ) − n ) + · · · + (2( n + n X i =1 p i ) − 2) + · · · + (2( n + n X i =1 p i ) − 1) n
atau
(2 n ( n + n X i =1 p i ) − ( n ( n + 1) 2 ) n = 2( n + n X i =1 p i ) − n + 1 2
atau
2 n X i =1 p i + 3 n − 1 2 = 3 n − 1 + 4 n X i =1 p i 2
maka
n X
i =1 p i x i = 1 2 Ã 3 n − 1 + 4 n X i =1 p i ! n X i =1 p i (8)
Sedangkan S v + S e sama seperti Persamaan 5, yaitu
S v + S e = 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) (9)
Jika Persamaan (9) dan Persamaan (8) disubstitusikan ke Persamaan (7), men- jadi
ke ≤ 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) + 1 2 Ã 3 n − 1 + 4 n X i =1 p i ! n X i =1 p i
atau bilangan ajaibnya adalah
k ≤ 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) + 1 2 Ã 3 n − 1 + 4 n X i =1 p i ! n X i =1 p i ( n + n X i =1 p i ) − 1 ¥ (10)

## 3. Penutup
Dari uraian diatas dapat ditarik kesimpulan, bahwa batas minimal bilangan ajaib dari pelabelan total edge-magic dari graph caterpillar adalah
k ≥ 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) + n + 1 2 n X i =1 p i ( n + n X i =1 p i ) − 1
dan batas maksimal bilangan ajaib dari pelabelan total edge-magic dari graph caterpillar adalah
k ≤ 2(( n + n X i =1 p i ) − 1)( n + n X i =1 p i ) + 1 2 Ã 3 n − 1 + 4 n X i =1 p i ! n X i =1 p i ( n + n X i =1 p i ) − 1

## Pustaka
[1] Chairul Imron, Variasi Pelabelan Graph Lintasan dan Star, Seminar Nasional Matematika ITS, 4 Desember 2004.
[2] Chairul Imron, Several Ways to Obtain Edge-Magic Total Labelings of Cater- pillars, International Workshop on Graph Labeling, Batu, Malang, 6-9 De- sember 2004.
[3] E.T. Baskoro, Pelabelan Total Sisi Ajaib Prosiding Konferensi Nasional Matematika XI Bagian I (2002) 281-285.
[4] E.T. Baskoro, Critical Sets in Edge-Magic Total Labelings. 2005.
[5] J. Sedlacek, problem 27, Theory of Graphs and it’s Applications (Smolenice, 1963), 163-164, Publ. House Czechoslovak Acad. Sci.,Prague, 1964).
[6] A. Kotzig and A. Rosa, Magic Valuations of Finite Graph, Canad. Math. Bull. 13 (1970), 451-461.
[7] W.D. Wallis, Magic Graphs , Birkhauser Boston, 2001.