Abstrak
PELABELAN PADA GRAF STAR, FIRECRACKER, DAN BANANA TREE BERDASARKAN KONDISI JARAK
Oleh :
ADI PRAKOSO - M0104013 -
ABSTRAK
Adi Prakoso, 2009. PELABELAN PADA GRAF STAR, FIRECRACKER, DAN
BANANA TREE BERDASARKAN KONDISI JARAK. Fakultas Matematika dan Ilmu
Pengetahuan Alam. Universitas Sebelas Maret.
Masalah pengiriman paket pesan dalam jaringan radio dapat diformulasikan
dalam pelabelan graf berdasarkan pada jarak yang dinotasikan L(d1,d2). Untuk (d1,d2)
bilangan bulat non negatif, pelabelan graf adalah pemetaan yang membawa elemen–
elemen graf ke bilangan bulat non negatif. Menurut Jin dan Yeh [3], L(d1,d2)-labelling
graf G, adalah suatu fungsi f : V(G) →{ 0, 1, 2, . . . } sedemikian sehingga
| f(u) – f(v)| ≥ di, dimana , ( ) u v V G Œ dan jarak antara u dan v adalah i dalam graf G,
untuk i = 1, 2. Bilangan L(d1,d2) dalam G, )(
21 ,
G dd l adalah bilangan k terkecil
sedemikian sehingga terdapat sebuah label L(d1,d2) dengan k adalah label terbesar.
Dari hasil pembahasan, diperoleh kesimpulan bahwa
1 2 ,
( ) d d G l dengan
1 2 ( , ) {(0,1), (1,1), (1, 2)} d d Œ untuk graf star, firecracker, dan banana tree masing-
masing adalah sebagai berikut
1. ( 2)( 1,0 - = nSn l , 1)( 1,1 -=nSn l , 42)( 2,1 -= nSn l ), n ≥ 4.
2. ( 2)( )4,(1,0 = n F l , 3)( )4,(1,1 = n F l , 5)( )4,(2,1 = n F l ), n ≥ 2.
3.
Ó
Ì
Ï
³-
=
=
4,1
32,2
)( )4,(1,0
nn
dann
B n l ,
Ó
Ì
Ï
³
=
=
4,
32,3
)( )4,(1,1
nn
dann
B n l ,
Ó
Ì
Ï
³-
=
=
4,22
32,4
)( )4,(2,1
nn
dann
B n l .
Kata kunci: pelabelan graf, L(d1, d2), star, firecracker, banana tree.