ABSTRAK
Misal G adalah graf terhubung dengan himpunan vertex V (G) dan him- punan edge E(G). Untuk setiap pasangan vertex u, v ? V (G), interval antara u dan v merupakan kumpulan vertex yang terdapat pada path terpendek u ? v. Suatu vertex s ? V (G) disebut sebagai pembeda kuat untuk dua vertex u dan v jika u terdapat pada path terpendek v ? s, dinotasikan dengan u ? I [v, s] atau v terdapat pada path terpendek u ? s, dinotasikan dengan v ? I [u, s]. Himpunan vertex S dikatakan himpunan pembeda kuat dari G jika untuk setiap dua vertex di G dibedakan kuat oleh suatu vertex di S. Basis metrik kuat adalah himpunan pembeda kuat dengan kardinalitas minimum. Dimensi metrik kuat pada suatu graf G sdim(G) didefinisikan sebagai kardinalitas dari basis metrik kuat.
Dalam penelitian ini dicari dimensi metrik kuat pada graf broken fan, graf starbarbell, dan graf Cm ?k Pn . Metode penelitian yang digunakan dalam peneli- tian ini adalah kajian pustaka.
Hasil penelitian menyatakan bahwa dimensi metrik kuat pada graf broken fan adalah sdim(BF (a, b)) = 3, untuk a = 2 dan b = 2, dan sdim(BF (a, b)) = a+b?2, untuk a ? 2 dan b ? 3. Dimensi metrik kuat pada graf starbarbell dengan
mi ? 3 dan n ? 2 adalah sdim(SBm ,m ,...,m ) = ?n (mi ? 1) ? 1. Dimensi
metrik kuat pada graf Cm ?k Pn terdiri dari dua kasus, yaitu sdim(Cm ?k Pn)
= (mn(n + 1)k?1 ) ? 1 untuk m ? 3, n = 2, dan k ? 1, dan sdim(Cm ?k Pn ) =
(mn(n + 1)k?1) ? 2 untuk m ? 3, n ? 3, dan k ? 1.
Kata Kunci: dimensi metrik kuat, himpunan pembeda kuat, graf broken fan, graf starbarbell, graf Cm ?k Pn
