DIMENSI METRIK DAN NON-ISOLATED RESOLVING NUMBER PADA BEBERAPA GRAF KHUSUS

Abstract

Pada tahun 1736 lahirlah teori graf melalui makalah tulisan seorang ahli matematikawan berasal dari Swiss yang bernama Leonhard Euler. Euler berhasil memecahkan teka-teki masalah jembatan Konigsberg yang sangat terkenal. Teori graf memiliki kajian yang cukup menarik untuk dipelajari, salah satunya yaitu dimensi metrik (metric dimension). Dimensi metrik pertama kali diperkenalkan oleh Slater pada tahun 1975 yang kemudian dikembangkan lagi oleh Harary dan Melter pada tahun 1976. Dimensi metrik adalah kardinalitas minimum himpunan pembeda pada G. Jarak dari vertex u ke vertex v, dinotasikan dengan d(u; v). Himpunan terurut W = fW1;W2;W3,..., Wkg dari vertices dalam graf terhubung terhadap W adalah k-vektor (pasangan k-tuple) r(vjW) = (d(v;w1); d(v;w2),..., d(v;wk)). Sebuah himpunan pembeda W pada graf G dikatakan himpunan pembeda tak terisolasi (non-isolated resolving set) jika subgraf (W) diinduksi oleh titik (simpul) tak terisolasi. Kardinalitas minimum dari himpunan pembeda tak terisolasi pada suatu graf dikatakan non-isolated resolving number yang dinotasikan dengan nr(G) (Chitra dan Arumugam, 2010).