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.