Pelabelan Komposit pada Graf Pohon

Abstract

Pelabelan komposit merupakan fungsi bijektif dari himpunan simpul dan sisi pada graf ke himpunan bilangan bulat positif sedemikian sehingga setiap sisi yang bertetangga memiliki label yang tidak relatif prima. Graf yang memenuhi syarat tersebut disebut graf komposit. Penelitian ini bertujuan membuktikan bahwa beberapa kelas graf pohon merupakan graf komposit. Kelas graf yang dikaji meliputi graf sisir, graf pohon Y, graf sapu, graf ulat teratur, graf hasil identifikasi simpul dua graf bintang homogen, graf H bintang, dan graf ilalang. Penelitian ini menggunakan pendekatan deduktif aksiomatik, yaitu melalui penyusunan konstruksi fungsi pelabelan dan pembuktian formal berdasarkan definisi serta teorema yang berlaku dalam teori graf. Proses penelitian diawali dengan analisis struktur masing-masing graf untuk mengidentifikasi keteraturan matematis yang mendukung pembentukan fungsi pelabelan. Selanjutnya, dirumuskan dugaan (konjektur) yang kemudian dibuktikan secara deduktif sehingga diperoleh hasil yang sahih. Hasil menunjukkan bahwa seluruh graf yang diteliti terbukti merupakan graf komposit. Penelitian ini memberikan kontribusi terhadap pengembangan pelabelan graf serta membuka peluang kajian lebih lanjut terhadap kelas graf lainnya.