Perpustakaan Digital ITB

Misalkan k ? N dan ? = {S1, S2, ..., Sk} adalah suatu partisi terurut dari himpunan titik V (G) pada graf G. Untuk setiap v ? V (G), koordinat terhadap partisi ? didefinisikan sebagai r(v, ?) = (d(v, S1), d(v, S2), ..., d(v, Sk)) dengan d(v, Si) = min{d(u, v) : v ? Si). Partisi ? disebut partisi pembeda jika untuk setiap u, v ? V (G), r(u, ?) ?= r(v, ?). Dimensi partisi graf G, dinotasikan ?p(G), adalah nilai minimum dari kardinalitas partisi pembeda pada G. Jika partisi ? juga memenuhi untuk setiap v ? V (G), terdapat Si ? ? sehingga d(v, Si) = 1, maka ? disebut partisi dominasi pembeda. Dimensi partisi dominasi, dinotasikan ?p(G), adalah nilai minimum dari kardinalitas partisi dominasi pembeda pada graf G. Penelitian ini menggunakan metode studi literatur dan pendekatan analitis untuk menentukan nilai ?p(G) dan ?p(G) pada graf hasil kali Kartesius G×Pk, dengan G merupakan graf lengkap Km dan graf kincir angin Perancis Wnm . Hasil penelitian menunjukkan bahwa untuk graf Km × Pn dengan m ? 5 dan n ? 2, diperoleh batas atas ?p(Km × Pn) ? ??? ?? 2a ? 1, m = a2, a ? 3 2a, m ? [a2 + 1, a2 + a], a ? 2 2a + 1, m ? [a2 + a + 1, a2 + 2a], a ? 2. dan ?p(Km × Pn) ? ??? ?? 2a ? 1, m = a2, a ? 3 2a, m ? [a2 + 1, a2 + a], a ? 2 2a + 1, m ? [a2 + a + 1, a2 + 2a], a ? 2. Lebih jauh lagi, untuk m, n ? N dan n ? 2 diperoleh nilai eksak ?p(Km × Pn) = ( 3, m = 3 4, m ? [4, 6] dan ?p(Km × Pn) = 4 untuk m ? [4, 6]. Kemudian, untuk graf kincir angin Perancis Wnm diperoleh ?p(Wnm ) = ?p(Wnm ) = a, a ? 1 m ? 1 + 1 ? n ? a m ? 1 , ?p(Wnm × Pk) ? a, a ? 1 m ? 1 + 1 ? n ? a m ? 1 , dan ?p(Wnm × Pk) ? a + 1, a ? 1 m ? 1 + 1 ? n ? a m ? 1 .