BILANGAN PELABELAN-L(j,k) PADA GRAF PATH KUADRAT

MOHAMAD FAHRULI WAHYUJATI, Dr.rer.nat Yeni Susanti, M.Si.

2018 | Skripsi | S1 MATEMATIKA

Diberikan bilangan bulat positif j dan k. Suatu pelabelan-L(j,k) pada suatu graf merupakan permasalahan kode penugasan titik-titik dari graf tersebut ke suatu bilangan bulat non negatif sedemikian hingga label dari titik-titik yang saling bertetangga mempunyai selisih sekurang-kurangnya j, serta label dari titik-titik yang berjarak dua mempunyai selisih sekurang-kurangnya k. Untuk sebarang pelabelan-L(j,k) f pada graf G, span f didefinisikan sebagai selisih antara nilai label maksimum dan nilai label minimum yang ditentukan oleh pelabelan f pada graf G. Bilangan pelabelan-L(j,k) pada graf G, dinotasikan dengan Lamda_{j,k}(G), merupakan span minimum dari semua pelabelan-L(j,k) yang mungkin dari graf G. Graf P_n = v_0v_1v_2...v_{n-2}v_{n-1} merupakan graf yang terdiri dari path tunggal. Graf P_n kuadrat, dinotasikan dengan P_n^2, adalah graf yang didapat dengan cara menghubungkan titik-titik pada graf P_n yang berjarak paling banyak 2. Dalam skripsi ini dicari bilangan pelabelan-L(j,k) pada graf P_n^2 untuk j kurang dari atau sama dengan k.

Given any positive integer j and k, the L(j,k)-labeling problem consists in a code assignment of nonnegative integers to the vertices of a graph such that adjacent vertices receive values which differ by at least j, and vertices connected by a 2 length path receive values which differ by at least k. The span of f is the difference between the maximum and the minimum numbers assigned by f. The L(j,k)-labeling number of G, denoted by Lamda_{j,k}(G), is the minimum span over all L(j,k)-labelings of G. Given graph P_n = v_0v_1v_2 ... v_{n-2}v_{n-1} denotes the path of order n. The square of graph P_n, denoted by P_n^2, is the graph with the vertex set of P_n in which two vertices are adjacent when their distance in P_n is at most 2. Hence in this final project, we will find out the L(j,k)-labeling numbers of P_n^2 for j is less or equal k.

Kata Kunci : Graf, Pelabelan, Path, Penugasan kode, Graf path kuadrat