Perpustakaan Digital ITB

Konsep himpunan pembeda dari suatu graf pertama kali diperkenalkan oleh Slater (1975) dengan istilah locating set, dan oleh Harary dan Melter (1976) secara terpisah dengan nama resolving set. Kemudian konsep ini diperumum oleh Chartrand dkk. (1998) dengan mengenalkan partisi pembeda dari suatu graf. Chartrand dkk. (1998) melakukan pengelompokan titik dari graf G ke dalam sejumlah kelas partisi dan menghitung jarak setiap titik di G terhadap semua kelas partisi tersebut untuk mendapatkan representasi dari titik tersebut terhadap kelas partisi tersebut. Penelitian dalam dimensi partisi graf telah mendapatkan banyak perhatian. Sebagai hasil pertama, Chartrand dkk. (1998) menentukan dimensi partisi dari beberapa kelas pohon, yaitu graf bintang ganda dan graf ulat. Selanjutnya Chartrand dkk. (2000) mengkarakterisasi semua graf order n dengan dimensi partisi 2, n dan n-1 berturut- turut.