Perpustakaan Digital ITB

Misalkan G adalah graf berorientasi dengan orde n dan diameter d, serta D ? {0, 1, . . . d} adalah himpunan jarak pada G. Pelabelan D-ajaib pada graf berorientasi G adalah bijeksi f : V (G) ? {1, 2, . . . , n} di mana terdapat konstanta ajaib k sedemikian sehingga P y?ND(x) f(y) = k untuk setiap titik x di G, dengan ND(x) = {y|d(x, y) ? D}. Dalam tugas akhir ini, diberikan batas atas untuk konstanta ajaib k yang memperbaiki batas atas natural yang telah diketahui sebelumnya. Karakterisasi graf D-ajaib dengan konstanta ajaib terkecil dan konstruksi graf D-ajaib untuk sebagian besar konstanta ajaib yang mungkin juga akan disajikan. Selain itu akan dikaji