ABSTRAK

Maylinda Purna Kartika Dewi, 2016. DIMENSI PARTISI DARI GRAF LOLLIPOP, GRAF GENERALIZED JAHANGIR, DAN GRAF Cn ∗2 Km. Fa- kultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret.
Misalkan G adalah graf terhubung dengan himpunan vertex V (G) yang dapat dibagi menjadi beberapa partisi S. Himpunan Π dengan S ∈ Π dise- but partisi pembeda dari graf G jika setiap vertex di G mempunyai representasi berbeda terhadap Π dan Π merupakan himpunan dari k−partisi yang terurut. Kardinalitas minimum dari k−partisi pembeda terhadap V (G) disebut dimensi partisi pada graf G yang dinotasikan dengan pd(G). Graf lollipop Lm,n adalah graf lengkap Km dan graf lintasan Pn yang dihubungkan dengan sebuah bridge. Graf generalized Jahangir adalah graf yang terdiri dari cycle Cmn dengan 1 vertex tambahan yang adjacent dengan n vertex dari Cmn dengan m jarak yang sama di Cmn. Graf Cn ∗2 Km adalah suatu graf hasil dari operasi amalgamasi edge atau menggabungkan salah satu edge pada Cn dan satu edge pada Km. Beberapa pe- neliti telah menentukan dimensi partisi pada beberapa kelas graf. Hal ini menjadi acuhan untuk meneliti beberapa kelas graf yang belum diteliti sebelumnya. Dalam penelitian ini ditentukan dimensi partisi dari kelas graf lollipop Lm,n, graf generalized Jahangir Jm,n, dan graf Cn∗2 Km. Metode penelitian yang digu- nakan dalam penelitian ini adalah kajian pustaka. Hasil penelitian menyatakan bahwa dimensi partisi dari graf lollipop adalah pd(Lm,n) = m untuk m ≥ 3 dan n ≥ 1. Dimensi partisi dari graf generali- zed Jahangir terdiri dari dua kasus, yaitu pd(Jm,n) = 3 untuk n = 3,4,5 dan pd(Jm,n) = ⌊n 2⌋+ 1 untuk n ≥ 6. Dimensi partisi dari graf Cn ∗2 Km terdiri daridua kasus, yaitu pd(Cn∗2 Km) = 3 untuk m = 2,3,4, dan pd(Cn∗2 Km) = m−1untuk m ≥ 5.

Kata Kunci: dimensi partisi, partisi pembeda, graf lollipop, graf generalized Jahangir, graf Cn ∗2 Km