Perpustakaan Digital ITB

MisalkanG = (V;E) suatu graf terhubung tak trivial. Pelabelan L(3; 2; 1) pada graf G merupakan fungsi f : V ! N [ f0g sehingga jf(u) ???? f(v)j 3 untuk setiap u; v 2 V dengan d(u; v) = 1, jf(u) ???? f(v)j 2 untuk setiap u; v 2 V dengan d(u; v) = 2, dan jf(u) ???? f(v)j 1 untuk setiap u; v 2 V dengan d(u; v) = 3. Untuk suatu k bilangan asli, pelabelan k????L(3; 2; 1) merupakan pelabelan L(3; 2; 1) dimana setiap label titik tidak lebih dari 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). Pada tesis ini ditentukan nilai 3;2;1 pada graf buku Bn, graf lintasan Pn yang diekspansi oleh graf buku Bm, serta graf lintasan Pn yang diekspansi oleh graf siklus Cm.