Perpustakaan Digital ITB

Misalkan W = {w1, w2,..., wk} merupakan subhimpunan verteks berkardinalitas k dari graf G. Representasi metrik lokal verteks v (terhadap W) pada G didefinisikan sebagai; r(v|W) = (d(v, w1), d(v, w2),..., d(v, wk)) dengan d(v, wi) didefinisikan sebagai jarak antara verteks v dan wi¬ dengan 1 ≤ i ≤ k. Jika r(u|W) ≠ r(v|W) untuk setiap pasang verteks bertetangga u, v pada G, maka W disebut sebagai himpunan pembeda lokal dari G. Bilangan k minimal sehingga W himpunan berkardinalitas k masih merupakan himpunan pembeda lokal pada G disebut dimensi metrik lokal dari G, dinotasikan sebagai lmd(G) dan W disebut basis metrik lokal dari G. Dalam tugas akhir ini dibahas dimensi metrik lokal dari graf Petersen diperumum.