Perpustakaan Digital ITB

Konsep dimensi partisi suatu graf pertama kali diperkenalkan oleh Chartrand, dkk, (1998). Konsep ini merupakan pengembangan dari konsep dimensi metrik yang telah dicetuskan oleh Slater (1975) serta Harary dan Melter (1976). Konsep ini memiliki beberapa aplikasi diantaranya dalam representasi senyawa kimia, permasalahan pengenalan pola, pengolahan citra, struktur data, dan navigasi robot pada lintasan tertentu (Yero dkk., 2011). Misalkan G(V,E) suatu graf terhubung dan Π = {L1,L2,...,Lk} suatu partisi dari V (G). Representasi simpul v terhadap partisi Π adalah suatu vektor yang komponen-komponennya merupakan jarak simpul v ke kelas-kelas partisi di Π. Bila representasi dari semua simpul berbeda maka partisi Π disebut sebagai partisi pembeda dari G. Dimensi partisi dari G adalah bilangan bulat k terkecil sehingga G mempunyai partisi pembeda dengan k kelas partisi. Kajian tentang dimensi partisi graf telah banyak didiskusikan,diantaranya karakterisasi graf berdasarkan dimensi partisinya. Graf dengan dimensi partisi 2 hanyalah graf lintasan. Graf dengan dimensi partisi sama dengan ordenya hanyalah graf lengkap. Sedangkan graf berorde n dengan dimensi partisi n−1 adalah salah satu graf K1,n−1, Kn −e, atau K1 + (K1 ∪Kn−2), dan terdapat 23 graf tidak isomorfik yang memiliki dimensi partisi n−2. Dimensi partisi untuk graf hasil kali operasi telah dikaji oleh beberapa peneliti, antara lain graf hasil operasi korona, hasil kali kuat, dan hasil kali kartesius. Pada disertasiini,kami menentukan dimensi partisi grafhasil operasi subdivisi pada sisi sisinya.Adapun hasilnya,diperoleh dimensi partisi graf hasil sub divisi satu sisi dari graf kembang api dan graf ulat. Secara umum, diberikan batas atas dimensi partisi grafhasilsub divisi dari sebarang graf terhubung. Selain itu,diperoleh juga dimensi partisi graf hasil subdivisi semua sisi dari graf lengkap dan graf bintang.