DIMENSI PARTISI GRAF GIR

Misalkan G = (V;E) adalah graf terhubung dan S V (G). Selanjutnyamisalkan terdapat titik v 2 V (G). Maka jarak titik v terhadap S didenisikan sebagaid(v; S) = minfd(v; x)jx 2 Sg. Misalkan himpunan titik V (G) dipartisi menjadi beberapapartisi, 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 vterhadap didenisikan sebagai r(vj) = (d(v; S1); d(v; S2); ; d(v; Sk)). Jika setiaptitik yang berbeda di G mempunyai representasi yang berbeda terhadap , maka disebut sebagai partisi penyelesaian. Kardinalitas minimum dari k-partisi penyelesaianterhadap V (G) disebut dengan dimensi partisi dari G, dinotasikan dengan pd(G).Misalkan terdapat graf siklus genap C2n; n 2: v0v1 ; v2n1v0. Graf gir G2ndiperoleh 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; ; v2n2. Misalkan dimensipartisi graf Gir pd(G2n) = k. Pada tulisan ini akan dikaji kembali bahwa banyaknyatitik di graf gir G2n dibatasi oleh dimensi partisinya, yaitu 2n + 1 < 3k4(k + 2)2k7.