Perpustakaan Digital ITB

Definisikan graf G dengan himpunan titik V (G) dan himpunan sisi E(G). Suatu titik di graf G mendominasi dirinya sendiri dan tetangganya. Himpunan titik D di graf G adalah himpunan dominasi jika setiap titik di G didominasi oleh titik-titik D. Lintasan x-y dengan panjang d(x, y) dikatakan geodesik x-y. Selang tertutup I[x, y] beranggotakan x, y dan semua titik yang berada pada geodesik x-y dari G. Himpunan titik S disebut himpunan geodetik jika I[S] = V (G). Sementara subhimpunan titik W dari graf G dikatakan himpunan dominasi geodetik jika W adalah himpunan dominasi sekaligus himpunan dominasi. Kardinalitas minimum dari himpunan dominasi geodetik pada graf G adalah bilangan dominasi geodetik, dinotasikan γg(G). Pada tugas akhir ini, kita mempelajari bilangan dominasi geodetik pada Graf Mycielski. Kita berusaha mendapatkan batas bawah dan batas atas bilangan dominasi geodetik pada Graf Mycielski.