PELABELAN JARAK DUA PADA BEBERAPA KELAS GRAF

Abstract

Penelitian ini membahas penentuan nilai minimum span pelabelan 𝐿 2 1 pada tiga kelas graf khusus, yaitu graf petasan 𝐹𝑚 𝑛)), graf mushroom ganda 2 𝑀𝑟𝑛)), dan graf splitting dari graf bintang 𝑆𝑝𝑙 𝐾1 𝑛)))). Pelabelan 𝐿 2 1 merupakan fungsi yang memberikan label bilangan bulat non-negatif pada setiap titik graf dengan ketentuan bahwa dua titik yang berjarak satu memiliki selisih label sedikitnya dua dan titik yang berjarak dua memiliki selisih label sedikitnya satu. Metode penelitian menggunakan pendekatan deskriptif aksiomatik untuk mendefinisikan sifat struktural tiap graf dan lemma pelabelan yang relevan, dilanjutkan dengan pendeteksian pola untuk mengidentifikasi keteraturan label yang muncul. Melalui analisis ini diperoleh konstruksi pola pelabelan yang memenuhi seluruh aturan serta membuktikan ketercapaian batas bawah nilai span. Hasil penelitian menunjukkan bahwa graf petasan memenuhi 𝜆2 11(𝐹𝑚 𝑛 𝑛 11, graf mushroom ganda memenuhi 𝜆2 11(2 𝑀𝑟𝑛 2 𝑛 22, dan graf splitting dari graf bintang memenuhi 𝜆2 11(𝑆𝑝𝑙(𝐾1 𝑛 2 𝑛 11. Temuan ini memberikan kontribusi pada pengembangan teori pelabelan graf, khususnya pada pelabelan 𝐿(2 1