ANALISA LOCATING INDEPENDENT DOMINATING SET PADA GRAF KHUSUS dan GRAF OPERASI COMB SISI

Abstract

Teori graf adalah cabang kajian matematika yang mempelajari sifat-sifat graf dimana graf terdiri dari himpunan benda-benda yang disebut simpul (Vertex) yang terhubung oleh sisi (Edge). Teori graf pertama kali diperkenalkan pada tahun 1736 oleh seorang matematikawan terkenal di swiss yang bernama Leonhard Euler. Teori graf berkembang dan meningkat pesat pada pertengahan 1960-an, salah satunya yaitu teori dominating set. Locating independent dominating set merupakan perluasan dari independent dominating set dan locating dominating set(1980) yang dikembangkan dari teori dominating set. Salah satu teori yang dikembangkan dalam teori graf adalah locating independent dominating set. Locating independent dominating set merupakan suatu konsep penentuan titik seminimal mungkin pada graf dengan ketentuan titik sebagai locating independent dominating set menjangkau semua titik yang ada disekitarnya dan tidak adjacent. Kardinalitas minimum dari locating independent dominating set disebut locating independen domination number yang disimbolkan dengan γLi(G). Saat ini locating independent dominating set tidak hanya dikembangkan pada graf khusus saja, tetapi juga diterapkan pada graf operasi. Graf operasi merupakan operasi terhadap dua graf atau lebih sehingga menghasilkan graf baru. Jenis-jenis graf operasi diantaranya operasi amalgamasi, comb product, shackle dan graf operasi comb sisi. Pada penelitian ini peneliti akan mengembangkan teori locating independent dominating set pada graf khusus dan graf operasi comb sisi. Tujuan penelitian ini adalah menentukan banyaknya titik dan sisi pada graf operasi comb sisi, menentukan locating independent dominating set dan nilai locating independent dominating set dari beberapa graf khusus dan operasi comb sisi sehingga dihasilkan 10 teorema baru, diantaranya adalah: 1. Teorema 4.1 Misal G adalah graf khusus berupa graf buku segiempat B4,n untuk n ≥ 2, maka Locating independent dominating number dari G adalah γLi (B4,n)=n 2. Teorema 4.2 Misal G adalah graf khusus berupa graf prisma H4,n untuk n ≥ 3 dan n genap, maka Locating independent dominating number dari G adalah γLi (H4,n)=2n. 3. Teorema 4.3 Misal G adalah graf khusus berupa graf roda Wn untuk n ≥ 6 dan n genap, maka Locating independent dominating number dari G adalah γLi (Wn)=n 2. 4. Teorema 4.4 MisalGadalah graf hasil operasi comb sisi dari graf bintangSm dan graf rodaWn untukm≥3n≥6dan n genap, makaγLi (SmDWn) = nm−2m 2 +1. 5. Teorema 4.5 Misal G adalah graf hasil operasi comb sisi dari graf bintang Sn dan graf lingkaran Cm untuk n≥3 m≥5 dan m ganjil, maka γLi (Sn DCm) = n(m−1) 2 . 6. Teorema 4.6 Misal G adalah graf hasil operasi comb sisi dari graf bintang Sn dan graf lintasan Pm untuk n ≥ 3 m ≥ 4 dan m genap, maka γLi (Sn DPm) = bn(m−1) 2 + 1c. 7. Teorema 4.7 Misal G adalah graf hasil graf operasi comb sisi dari graf lingkaran Cn dan graf ladder Lm untuk n≥3, m≥3 maka γLi (Cn DLm) = mn−n. 8. Teorema 4.8 Misal G adalah graf hasil graf operasi comb sisi dari graf lingkaran Cn dan graf lingkaran C3, untuk n≥3, maka γL (Cn DC3) = n. viii 9. Teorema 4.9 Misal G adalah graf hasil operasi comb sisi dari graf lintasan Pn dan graf lingkaran C3, untuk n≥3 maka γLi (Pn DC3) = n−1. 10. Teorema 4.10 Misal G adalah graf hasil operasi comb sisi dari graf lingkaran Cn dan graf lintasan Pm untuk n ≥ 3,m ≥ 6 dan m genap maka γLi (Cn DPm) =mn−2n 2 .