Nilai Minimal Span Pelabelan L(3,1) pada Graf Supercycle Sc(n,r)

Abstract

An labeling of a graph  is a function f from the set of vertex V(G) to the set of positive integers for any two vertices u, v where label difference |f(u)-f(v)|≥3 for distance d(u,v)=1 and label difference |f(u)-f(v)|≥1 for distance d(u,v)=2. In this study, the smallest positive integer λ where the maximum label used on L(3,1)-labeling for supercycle graph Sc(n,r) was formulated. The supercycle graph Sc(n,r) is the result of combining two special graphs, namely cycle graph  Cn and Hanoi graph Hr. To determine the formula for the minimum span value of labeling on supercycle graph, a pattern detection method is used, which is labeling several supercycle graph with certain n and r values, then we generalized. We obtained that λ(Sc(n,1))=6 if n= 1. Furthermore, λ(Sc(n,1))=7 if n>1 and even; λ(Sc(n,1))=8 if n>1 and odd. In addition, λ(Sc(n,r))=8, for r>1.

Keywords: L(3,1)-Labeling, Supercycle Graphs.

Abstrak

Pelabelan L(3,1) didefinisikan sebagai pemetaan dari himpunan titik pada graf G ke himpunan bilangan bulat positif dimana untuk setiap dua titik u,v jika d(u,v)=1 berlaku |f(u)-f(v)|≥3 dan jika d(u,v)=2 berlaku |f(u)-f(v)|≥1. Pada penelitian ini dirumuskan nilai minimal rentang (span) pelabelan L(3,1) untuk graf supercycle Sc(n,r), yang dinotasikan dengan λ(Sc(n,r)). Graf supercycle Sc(n,r) merupakan hasil dari penggabungan dua buah graf khusus, yaitu graf cycle Cn  dan graf Hanoi Hr.  Proses penentuan nilai minimal span dari pelabelan L(3,1) pada graf supercycle, digunakan metode pendeteksian pola, yaitu dilakukan pelabelan pada beberapa graf supercycle Sc(n,r) dengan nilai n dan r tertentu, kemudian digeneralisasi secara induksi. Hasil penelitian ini diperoleh nilai  λ(Sc(n,1))=6, jika n=1. Kemudian, λ(Sc(n,1))=7, jika n>1 dan n genap, λ(Sc(n,1))=8, jika n>1 dan n ganjil. Selanjutnya, λ(Sc(n,r))=8 untuk r>1.