Perpustakaan Digital ITB

Misalkan W = fw1;w2; :::;wkg merupakan subhimpunan titik berkardinalitas k dari graf G. Representasi metrik titik v terhadap W di G didefinisikan sebagai: r(vjW) = (d(v;w1); d(v;w2); :::; d(v;wk)) dengan d(v;wi) menyatakan jarak antara titik v dengan wi untuk suatu 1 i k. Jika untuk sebarang pasangan titik bertetangga u dan v di G berlaku r(ujW) 6= r(vjW), maka W disebut himpunan pembeda lokal dari G. Bilangan k terkecil sehingga W V (G) berkardinalitas k masih merupakan himpunan pembeda lokal dari G disebut dimensi metrik lokal dari G, dinotasikan sebagai lmd(G), dan W disebut sebagai basis metrik lokal dari G. Kemudian, misalkan n menyatakan orde dari graf G, l menyatakan banyaknya kelas ekuivalen kembar sejati dari G, dan d menyatakan diameter G. Maka, lmd(G) n ???? l serta lmd(G) n ???? d. Dalam tugas akhir ini, akan dibahas beberapa graf terhubung nontrivial G yang memenuhi lmd(G) = n ???? l atau lmd(G) = n ???? d: