Perpustakaan Digital ITB

Misalkan B={w_1,w_2,…,w_k}⊆V(G) adalah himpunan titik, dan x adalah sebarang titik pada graf G. Notasikan r(x) sebagai urutan parsial dari B, yaitu pengurutan subhimpunan titik pada B dalam urutan tak-turun oleh jaraknya terhadap x. Himpunan B disebut himpunan lokasi sentroidal dari graf G jika r(x)≠r(y), untuk setiap pasangan x,y titik berbeda. Basis sentroidal dari graf G adalah himpunan lokasi sentroidal dengan kardinalitas minimum. Notasikan CD(G) sebagai dimensi sentroidal dari G, yaitu kardinalitas dari basis sentroidal dari G. Dalam penelitian tesis ini akan dibahas dimensi sentroidal dari beberapa graf dan juga dimensi sentroidal dari graf sirkulan. Penelitian tesis ini juga membahas dimensi sentroidal dari hasil operasi dua graf, seperti operasi join dan operasi korona. Secara khusus akan dibahas dimensi sentroidal dari operasi kali tensor dan operasi kali kartesius antara graf lengkap K_ndan graf lintasan P_2. Selain itu dibahas juga algoritma dalam menentukan dimensi sentroidal dari graf secara umum dengan memanfaatkan matriks ketetanggaannya.