Perpustakaan Digital ITB

Misalkan G = (V;E) adalah suatu graf terhubung. Jarak antara dua titik u dan v di G yang dinotasikan dG(u; v) adalah panjang lintasan u ???? v terpendek. Misalkan W = fw1;w2; : : : ;wkg subhimpunan terurut tak kosong dari V (G) dan misalkan pula v sebarang titik di G. Representasi titik v terhadap W yang dinotasikan r(vjW) didefinisikan sebagai k-vektor (dG(v;w1); dG(v;w2); : : : ; dG(v;wk)). Jika untuk setiap dua titik yang bertetangga di G memiliki representasi yang berbeda terhadap W, maka W disebut himpunan pembeda lokal dari G. Himpunan pembeda lokal dari G dengan kardinalitas terkecil disebut basis metrik lokal dari graf G. Dimensi metrik lokal dari G adalah kardinalitas dari basis metrik lokal pada G dan dinotasikan dengan lmd(G). Dalam penelitian ini, ditentukan batas bawah dan batas atas dimensi metrik lokal dari graf garis, karakterisasi graf terhubung yang memiliki graf garis dengan dimensi metrik lokal 1, serta dimensi metrik lokal pada graf garis dari graf bintang, graf persahabatan, graf kipas, graf roda, graf ulat, dan graf hasil kali berakar.