DIMENSI PARTISI GRAF GIR

Abstract

Misalkan G = (V;E) adalah graf terhubung dan S V (G). Selanjutnya
misalkan terdapat titik v 2 V (G). Maka jarak titik v terhadap S didenisikan sebagai
d(v; S) = minfd(v; x)jx 2 Sg. Misalkan himpunan titik V (G) dipartisi menjadi beberapa
partisi, sebut S1; S2; ; Sk. Notasikan sebagai suatu himpunan terurut dari k-partisi,
tulis = fS1; S2; ; Skg. Misalkan terdapat suatu titik v di G. Maka representasi v
terhadap didenisikan sebagai r(vj) = (d(v; S1); d(v; S2); ; d(v; 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: v0v1 ; v2n􀀀1v0. Graf gir G2n
diperoleh dengan cara menambahkan satu titik baru, notasikan c, yang bertetangga den-
gan n buah titik di graf C2n; n 2, yaitu titik-titik v0; v2; ; v2n􀀀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.