Perpustakaan Digital ITB

Representasi multihimpunan rm(v|W) dari titik v di graf G terhadap himpunan W ? V (G) adalah multihimpunan jarak-jarak antara v dan semua titik-titik di W. Apabila rm(v|W) berbeda untuk setiap v di V (G), W disebut sebagai himpunan m?pembeda pada G. Kardinalitas terkecil dari suatu himpunan m?pembeda pada G disebut dimensi multihimpunan dari G, yang dinotasikan dengan md(G). Suatu subhimpunan W ? V (G) disebut himpunan dominasi pada G jika setiap titik di V (G) \ W bertetangga paling sedikit dengan satu titik di W. Kardinalitas terkecil dari suatu himpunan dominasi pada G disebut bilangan dominasi dari G, yang dinotasikan dengan ?(G). Termotivasi dengan memandang sifat yang berlawanan dari konsep himpunan m? pembeda, selanjutnya di sini disajikan gagasan himpunan baru yang disebut himpunan dominasi ajaib dengan semua titik di luar himpunan ini memiliki representasi multihimpunan yang sama. Himpunan ini benar-benar berkaitan dengan himpunan dominasi dari graf itu sendiri. Masalah optimasi yang menarik adalah menemukan himpunan dominasi ajaib terkecil atau secara ekuivalen mendapatkan sebanyak mungkin semua titik di luarnya yang memiliki representasi multihimpunan yang sama. Oleh karena itu, didefinisikan bilangan dominasi ajaib G, yang dinotasikan dengan ?m(G), sebagai kardinalitas terkecil dari suatu himpunan dominasi ajaib dari G. Dalam penelitian ini, disajikan batas-batas ?m(G) untuk sebarang graf G. Kemudian, juga dikarakterisasi graf-graf yang memiliki bilangan dominasi ajaib tertentu. Selain itu, untuk setiap dua bilangan bulat positif k dan n dengan n ? 3 dan 1 ? k ? n ? 1, ditunjukkan eksistensi graf G berorde n sehingga ?m(G) = k. Sebagai tambahan, ditentukan bilangan dominasi ajaib dari beberapa kelas graf.