digilib@itb.ac.id +62 812 2508 8800

Misalkan G adalah graf berorder n dan berdiameter d. Misalkan D?{0,1,2,…,d} dan N_D (v)={u?V(G) ?|d(u,v)?D} dengan v?V(G). Sebuah pemetaan bijeksi l?V(G)?{1,2,…,n} disebut pelabelan D-jarak ajaib dari G jika terdapat suatu bilangan nonnegatif k sedemikian sehingga ?_(u?N_D (v))??l(u)?=k untuk setiap v?V(G). Jika D={1}, pelabelan D-jarak ajaib disebut pelabelan jarak ajaib. Nilai eigen dari graf G adalah nilai eigen dari matriks ketetanggaannya. Penelitian utama pada tugas akhir ini adalah hubungan antara nilai eigen dari graf dan eksistensi pelabelan jarak ajaib pada graf tersebut. Graf yang dimaksud adalah graf regular, graf regular jarak, graf regular kuat, graf garis dari graf regular, dan graf yang diperoleh dari hasil kali dua buah graf regular. Perkalian graf yang dimaksud adalah perkalian kuat, kartesian, leksikographik, dan kroneker. Dengan menggunakan nilai eigen dari graf regular kuat, diperoleh syarat perlu dan cukup dari graf regular kuat agar memiliki pelabelan jarak ajaib. Dengan menggunakan suatu matriks yang memiliki sifat khusus, diperoleh pelabelan dari beberapa perkalian graf. Dengan menggunakan hasil penelitian terdahulu tentang graf hypercube dan dengan melihat graf hypercube sebagai graf regular jarak, diperoleh eksistensi pelabelan D-jarak ajaib pada graf hypercube.