Analisis Locating Dominating Set pada Graf Khusus dan Hasil Operasi Comb Sisi

Abstract

Matematika merupakan ilmu universal yang mendasari perkembangan teknologi dan mempunyai peran penting dalam menyelesaikan berbagai permasalahan. Salah satu cabang matematika yang bermanfaat untuk memecahkan masalah dalam kehidupan sehari-hari adalah teori graf. Meskipun pada awalnya graf digunakan untuk menyelesaikan suatu masalah, namun graf telah mengalami perkembangan yang sangat luas didalam teori graf itu sendiri, diantaranya adalah teori dominating set dan perluasan dari teori dominating set yaitu teori locating dominating set. Penerapan teori locating dominating set dimulai pada tahun 1980 oleh Slater dengan membuat sebuah kode lokasi perlindungan untuk beberapa fasilitas dengan menggunakan jaringan detektor. Locating dominating set diartikan sebagai himpunan titik D pada graf G = (V;E) yang memenuhi syarat N(u)\D ̸= ∅, N(v)\D ̸= ∅ dan N(u)\D ̸= N(v)\D untuk setiap pasangan titik yang berbeda u dan v pada V (G)􀀀D dimana N(u) adalah himpunan titik tetangga dari u dan N(v) adalah himpunan titik tetangga dari v. Kardinalitas minimum dari locating dominating set disebut location domination number yang disimbolkan dengan L(G). Data dalam penelitian ini berupa graf khusus yang dioperasikan comb sisi. Graf khusus yang digunakan yaitu graf matahari Sn, graf helm Hn, graf buku segitiga Btn, graf buku Bn, graf lintasan Pn, graf cycle Cn dan graf bintang Sn. Metode yang digunakan dalam penelitian ini adalah deskriptif aksiomatik. Pada penelitian ini dihasilkan 12 teorema baru terkait location domination number yaitu: Teorema 4.1 Misal G adalah graf khusus berupa graf buku segitiga Btn untuk n 2, maka location domination number pada graf G adalah L(Btn) = n. Teorema 4.2 Misal G adalah graf hasil operasi comb sisi dari graf lintasan Pm dan graf matahari Sn dengan sisi x1xn sebagai sisi cangkok di graf Sn untuk m 3 dan n 3, maka location domination number pada graf G adalah L(Pm D Sn) = mn 􀀀 n. Teorema 4.3 Misal G adalah graf hasil operasi comb sisi dari graf cycle Cm dan graf matahari Sn dengan sisi x1xn sebagai sisi cangkok di graf Sn untuk m 3 dan n 3, maka location domination number pada graf G adalah L(Cm D Sn) = mn. Teorema 4.4 Misal G adalah graf hasil operasi comb sisi dari graf bintang Sm dan graf matahari Sn dengan sisi x1xn sebagai sisi cangkok di graf Sn untuk m 3 dan n 3, maka location domination number pada graf G adalah L(Sm D Sn) = mn. Teorema 4.5 Misal G adalah graf hasil operasi comb sisi dari graf cycle Cm dan graf vii helm Hn dengan sisi x1xn sebagai sisi cangkok di graf Hn untuk m 3 dan n 3, maka location domination number pada graf G adalah L(Cm D Hn) = mn. Teorema 4.6 Misal G adalah graf hasil operasi comb sisi dari graf bintang Sm dan graf helm Hn dengan sisi x1xn sebagai sisi cangkok di graf Hn untuk m 3 dan n 3, maka location domination number pada graf G adalah L(Sm D Hn) = mn. Teorema 4.7 Misal G adalah graf hasil operasi comb sisi dari graf lintasan Pm dan graf buku segitiga Btn dengan sisi x1x2 sebagai sisi cangkok di graf Btn untuk m 4 dan n 2, maka location domination number pada graf G adalah L(Pm D Btn) = mn 􀀀 n 􀀀 1. Teorema 4.8 Misal G adalah graf hasil operasi comb sisi dari graf cycle Cm dan graf buku segitiga Btn dengan sisi x1x2 sebagai sisi cangkok di graf Btn untuk m 3 dan n 2, maka location domination number pada graf G adalah L(CmDBtn) = mn􀀀1. Teorema 4.9 Misal G adalah graf hasil operasi comb sisi dari graf bintang Sm dan graf buku segitiga Btn dengan sisi x1x2 sebagai sisi cangkok di graf Btn untuk m 3 dan n 2, maka location domination number pada graf G adalah L(Sm D Btn) = mn. Teorema 4.10 Misal G adalah graf hasil operasi comb sisi dari graf lintasan Pm dan graf buku Bn dengan sisi x1x2 sebagai sisi cangkok di graf Bn untuk m 3 dan n 2, maka location domination number pada graf G adalah

L(Pm D Bn) = mn 􀀀 n + 1. Teorema 4.11 Misal G adalah graf hasil operasi comb sisi dari graf cycle Cm dan graf buku Bn dengan sisi x1x2 sebagai sisi cangkok di graf Bn untuk m 3 dan n 2, maka location domination number pada graf G adalah L(Cm D Bn) = mn. Teorema 4.12 Misal G adalah graf hasil operasi comb sisi dari graf bintang Sm dan graf buku Bn dengan sisi x1x2 sebagai sisi cangkok di graf Bn untuk m 3 dan n 2, maka location domination number pada graf G adalah L(Sm D Bn) = mn + 1.