Perpustakaan Digital ITB

Gagasan partisi pembeda dominasi diperkenalkan oleh Hernando dkk. (2019) sebagai cara baru membedakan titik pada suatu graf berdasarkan partisi himpunan titik. Gagasan ini menggabungkan konsep partisi pembeda dan himpunan dominasi. Suatu partisi yang didefinisikan haruslah memenuhi syarat sebagai partisi pembeda sekaligus partisi dominasi. Misalkan G adalah suatu graf terhubung dan ! = {S1, S2, · · · , Sk} adalah partisi terurut dari himpunan titik graf G. Suatu partisi ! disebut partisi pembeda jika untuk setiap sepasang titik u dan v, jarak antara u dan Sj tidak sama dengan jarak v dan Sj untuk suatu Sj ? !. Suatu partisi pembeda ! dikatakan partisi pembeda dominasi jika untuk setiap titik u di G, jarak antara titik u dan suatu kelas partisi Sj ? ! adalah satu. Dimensi partisi ?p(G) adalah kardinalitas minimum dari suatu partisi pembeda di G. Sedangkan, dimensi partisi dominasi ?p(G) adalah kardinalitas minimum dari suatu partisi pembeda dominasi di G. Apabila suatu partisi pembeda ! dari G dibentuk berdasarkan pewarnaan lokasi c di G, yaitu c(u) ?= c(v) untuk sebarang titik u dan v bertetangga di G, maka kardinalitas ! disebut sebagai bilangan kromatik lokasi ?L(G) dari graf G. Saat memperkenalkan konsep dimensi partisi dominasi, Hernando dkk. (2019) juga menunjukkan hubungan antara dimensi partisi dan dimensi partisi dominasi, yaitu ?p(G) ? ?p(G) ? ?p(G) + 1. Sebagai perluasan dari konsep dimensi partisi dominasi, dalam disertasi ini dikaji keterkaitan antara dimensi partisi, dimensi partisi dominasi, dan bilangan kromatik lokasi. Hasilnya, hubungan ketiganya dinyatakan dalam bentuk ketaksamaan ?p(G) ? ?p(G) ? ?L(G). Selanjutnya, dalam disertasi ini diberikan pula kelurga graf G yang memenuhi ?p(G) = ?p(G). Hanya graf lengkap K2 yang memenuhi ?p(K2) = ?p(K2) = 2. Adapun graf yang memenuhi ?p(G) = ?p(G) = 3, adalah graf siklus dan graf yang bilangan kromatik lokasinya sama dengan 3. Lebih lanjut, diperoleh pula keluarga graf G yang memenuhi ?p(G) = ?p(G) = 3 tetapi bilangan kromatik lokasinya sama dengan 4. Selain itu, dalam disertasi ini diturunkan pula sifat-sifat graf yang memenuhi ?p(G) = ?p(G)+1. Lebih lanjut, diberikan pula karakterisasi graf pohon Tn dengan n ? 6 titik yang mempunyai ?p(Tn) = n ? t untuk suatu t ? [2, n 2 ). Salah satu masalah terbuka dalam penelitian dimensi partisi dominasi adalah karakterisasi graf dengan dimensi partisi dominasi n ? 3. Dalam disertasi ini, telah berhasil dikaraterisasi semua graf G orde n ? 11 yang mempunyai dimensi partisi dominasi yang sama dengan dimensi partisinya, yaitu n ? 3.