Bilangan Dominasi pada Graf Hasil Operasi

Abstract

Diberikan sebuah graf $G$ dengan himpunan titik $V(G)$ dan himpunan sisi $E(G)$. Himpunan $S \subseteq V(G)$ adalah \emph{dominating set} dari graf $G$ jika setiap titik di $V(G)$ bertetangga dengan sebuah titik di $S$. \emph{Domination Number} $\gamma(G)$ adalah kardinalitas terkecil dari sebuah \emph{dominating set}. Nilai dari \emph{domination number} lebih kecil dari kardinalitas titik pada graf $G$, $\gamma(G)<|V(G)|$. Penelitian ini mengembangkan teori \emph{dominating set} pada beberapa graf yang merupakan hasil operasi terhadap dua graf khusus, yaitu $C_{n}$, $P_{n}$ dan $S_m$ . Operasi graf yang digunakan adalah join $C_n+S_m$, join $P_n + C_m$, tensor $P_2\bigotimes C_n$, dan komposisi $P_n[C_3]$. Hasil dari penelitian ini menunjukkan bahwa \emph{Domination Number} yang dihasilkan mencapai batas bawah dari $\gamma(G)$.