DIMENSI PARTISI GRAF GIR
Abstrak: Misalkan G = (V,E)
adalah graf terhubung dan S ⊆ V
(G). Selanjutnya misalkan terdapat titik ðœ ϵ V
(G). Maka jarak titik ðœ terhadap S didefinisikan sebagai d(ðœ, S) =
min{d(ðœ, x)|x ϵ S}. Misalkan himpunan titik V (G) dipartisi menjadi
beberapa partisi, sebut S1, S2, ..., Sk. Notasikan 𜋠sebagai suatu himpunan
terurut dari k-partisi, tulis 𜋠= { S1, S2,
..., Sk}. Misalkan terdapat suatu titik ðœ di G. Maka representasi ðœ
terhadap ðœ‹didefinisikan sebagai r(ðœ|ðœ‹) = (d(ðœ, S1), d(ðœ, S2),
..., d(ðœ, Sk)). Jika setiap titik yang berbeda di G mempunyai
representasi yang berbeda terhadap ðœ‹, maka 𜋠disebut
sebagai partisi penyelesaian. Kardinalitas minimum dari k-partisi penyelesaian
terhadap V (G) disebut dengan dimensi partisi dari G, dinotasikan dengan pd(G).
Misalkan terdapat graf siklus genap C2n, n ≥ 2: ðœ0ðœ1 ..., ðœ2n–1ðœ0. Graf gir G2n diperoleh dengan cara
menambahkan satu titik baru, notasikan c, yang bertetangga dengan n buah titik
di graf C2n, n ≥ 2, yaitu titik-titik ðœ0, ðœ2, ..., ðœ2n–2. Misalkan
dimensi partisi graf Gir pd(G2n) = k. Pada tulisan ini akan dikaji kembali
bahwa banyaknya titik di graf gir G2n dibatasi oleh dimensi partisinya, yaitu
2n + 1 < 3k4(k + 2)2k–7.
Penulis: REFINA RIZA
Kode Jurnal: jpmatematikadd120198
