Perpustakaan Digital ITB

Suatu himpunan terurut W disebut himpunan pembeda lokal di graf G jika setiap dua titik yang bertetangga di G memiliki representasi yang berbeda terhadap W. Kardinalitas minimum dari himpunan pembeda lokal di G disebut dimensi metrik lokal dari G, dinotasikan lmd(G). Untuk suatu graf G dengan himpunan titik V(G)={v_1, v_2,…,v_n} dan himpunan sisi E(G), graf Mycielski dari G, dinotasikan μ(G), adalah graf dengan himpunan titik V(μ(G))={x_1,…,x_n,y_1,…,y_n,z} dan himpunan sisi {x_i x_j| v_i v_j∈E(G)}∪{x_i y_j| v_i v_j∈E(G)}∪{y_i z| 1≤i≤n}. Pada proyek ini, ditentukan batas bawah dan batas atas dari dimensi metrik lokal untuk graf Mycielski dari suatu graf terhubung G.