Dimensi Metrik Lokal pada Graf Garis dari Graf Persahabatan

Abstract

Diberikan suatu graf terhubung G=(V(G), E(G)) dengan V(G) adalah himpunan titik dan E(G) adalah himpunan sisi di G. Misalkan W={w_1, w_2, ..., w_k} subhimpunan terurut tak kosong dari V(G). Untuk sebarang titik v di G, representasi titik v terhadap W yang dinotasikan r(v|W) didefinisikan sebagai k-vektor (d_G(v,w_1), d_G(v,w_2), ..., d_G(v,w_k)) dengan d_G(v,w_i) adalah panjang lintasan v-w_i terpendek untuk i=1,2, ..., k. Bilangan kardinal k dari W yang minimum sehingga untuk setiap dua titik yang bertetangga di G memiliki representasi yang berbeda disebut sebagai dimensi metrik lokal dari G, dinotasikan dengan lmd(G). Graf garis L(G) dari graf G adalah graf yang dikonstruksi dengan mengambil semua sisi di G sebagai titik-titik pada L(G), dan dua titik pada L(G) bertetangga jika kedua sisi pada G yang bersesuaian dengan kedua titik tersebut mempunyai titik bersama. Graf persahabatan F_n dengan 2n+1 titik adalah graf yang diperoleh dengan menggabungkan n salin C_3 dengan satu titik bersama. Dalam artikel ini diperoleh bahwa dimensi metrik lokal pada graf garis dari graf persahabatan adalah lmd(L(F_n))=2n-1.

Kata kunci: dimensi metrik lokal, graf garis, graf persahabatan.