Perpustakaan Digital ITB

Konsep dimensi partisi pada suatu graf terhubung diperkenalkan oleh Chartrand dkk. [12] pada tahun 1998. Konsep ini merupakan perluasan dari konsep dimensi metrik yang diperkenalkan oleh Slater [24] pada tahun 1975, dan Harary & Melter [9] pada tahun 1976. Dimensi partisi pada suatu graf G didefinisikan sebagai kardinalitas minimum suatu partisi terurut dari himpunan simpul V (G) sedemikian sehingga setiap simpul mempunyai representasi yang berbeda terhadap partisi tersebut. Dalam hal ini, representasi suatu simpul dinyatakan oleh jarak simpul tersebut terhadap kelas-kelas partisi. Penentuan dimensi partisi suatu graf secara umum tergolong persoalan NP-hard [14]. Artinya tidak terdapat algoritma yang efisien untuk menentukan dimensi partisi sebarang graf. Oleh karena itu kajian dalam menentukan dimensi partisi graf dilakukan dengan membatasi untuk kelas graf tertentu atau dengan mengkarakterisasi graf yang memenuhi suatu dimensi partisi yang diberikan. Beberapa hasil yang telah diperoleh adalah karakterisasi graf berorde n yang memiliki dimensi partisi 2; n; n-1 pada [13], dan yang memiliki dimensi partisi n-2 pada [19]. Selain itu dimensi partisi untuk beberapa kelas graf juga telah banyak ditemukan. Terdapat juga hasil kajian dimensi partisi untuk graf baru hasil operasi korona pada [4, 5, 8, 7] dan perkalian kartesian pada [15]. .......