Perpustakaan Digital ITB

Misalkan G=(V,E) adalah suatu graf terhubung tak trivial. Pelabelan L(3,2,1) pada graf G merupakan fungsi f:V→ N ∪{0} sehingga |f(u)-f(v)|≥ 3 untuk setiap u,v∈ V dengan d(u,v)=1, |f(u)-f(v)|≥ 2 untuk setiap u,v∈ V dengan d(u,v)=2, dan |f(u)-f(v)|≥ 1 untuk setiap u,v∈ V dengan d(u,v)=3. Untuk suatu k bilangan bulat tak negatif, pelabelan k-L(3,2,1) merupakan pelabelan L(3,2,1) dimana setiap label titik tidak lebih besar daripada k. Bilangan L(3,2,1) pada suatu graf G, dinotasikan dengan λ_3,2,1 (G), merupakan bilangan terkecil k sehingga graf G memiliki pelabelan k-L(3,2,1). Misalkan G dan H graf terhubung tak trivial. Hasil kali Cartesius dari graf G dan H, dinotasikan dengan G□H adalah graf dengan himpunan titik V(G□H)=V(G)× V(H) dengan (u_1,v_1) dan (u_2,v_2) bertetangga jika dan hanya jika u_1=u_2 dan v_1 v_2∈ E(H) atau v_1=v_2 dan u_1 u_2∈ E(G). Pada tesis ini ditentukan nilai λ_3,2,1 pada graf Jahangir, graf ulat dan hasil kali Cartesius graf ulat teratur dan graf lintasan.