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 ; v2n1v0. 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; ; v2n2. 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)2k7.
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 ; v2n1v0. 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; ; v2n2. 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)2k7.
Full Text:
PDFDOI: https://doi.org/10.25077/jmu.1.2.21-27.2012
Refbacks
- There are currently no refbacks.
Copyright (c) 2016 Jurnal Matematika UNAND
Ciptaan disebarluaskan di bawah Lisensi Creative Commons Atribusi-BerbagiSerupa 4.0 Internasional.