Pelabelan L(2.1) pada GRAF Crown (Crn) dan Graf Firecracker (Fm,n)

Abstract

Pelabelan L(2,1) pertama kali diperkenalkan oleh Griggs dan Yeh pada tahun 1992 sebagai pengembangan dari permasalahan penugasan frekuensi yang diajukan oleh Hale pada tahun 1980. Pelabelan L(2,1) adalah pemetaan untuk � �:𝑉(𝐺) → ℤ≥0 dengan syarat |𝑓(𝑢)−𝑓(𝑣)| ≥ 2 untuk titik bertetangga atau berjarak satu dan |𝑓(𝑢) − 𝑓(𝑣)| ≥ 1 untuk titik berjarak dua, dengan nilai minimum span dinotasikan 𝜆2,1(𝐺). Kajian pelabelan L(2,1) pada graf crown (𝐶𝑟𝑛) dan graf firecracker (𝐹𝑚,𝑛) masih belum banyak dilakukan, padahal keduanya memiliki struktur khas yang menarik untuk dianalisis. Graf crown diperoleh dari graf bipartit lengkap 𝐾𝑛,𝑛 dengan menghapus suatu perfect matching, sedangkan graf firecracker diperoleh dari 𝑚 buah graf bintang 𝑆1,𝑛 yang dihubungkan membentuk lintasan melalui satu titik daun tiap bintang. Penelitian ini menggunakan metode konstruktif dengan pendekatan pattern labeling, yaitu menentukan batas bawah span berdasarkan struktur graf, membangun pola pelabelan pada beberapa objek graf crown dan firecracker, menggeneralisasi pola tersebut, kemudian membuktikannya melalui batas bawah dan batas atas hingga diperoleh nilai minimum span dalam bentuk teorema. Hasil penelitian menunjukkan graf crown memiliki nilai minimum span � �2,1(𝐶𝑟𝑛) = 2𝑛 −2, karena pasangan titik (𝑢ᵢ,𝑣ᵢ) hasil penghapusan perfect matching tidak bertetangga sehingga dapat diberi label sama, sedangkan pasangan berbeda harus dipisahkan minimal dua satuan. Adapun graf firecracker memiliki nilai minimum span 𝜆2,1(𝐹𝑚,𝑛) = 𝑛 + 2, di mana span meningkat linear terhadap jumlah titik daun (𝑛) dan tidak dipengaruhi jumlah salinan graf bintang (𝑚).