Bilangan Fibonacci Berdasarkan Himpunan Bebas Graf Dayung Kayak

Abstrak

Konsep bilangan Fibonacci suatu graf G, yang didefinisikan oleh Prodinger dan Tichy pada tahun 1982 sebagai banyaknya himpunan bebas pada G, menyediakan landasan penting dalam teori graf. Himpunan bebas adalah himpunan simpul di mana tidak ada dua simpul yang saling bertetanggaan. Telah diketahui bahwa bilangan Fibonacci untuk graf lintasan P_n adalah F_n+2​ dan untuk graf siklus C_n adalah bilangan Lucas L_n. Penelitian ini bertujuan untuk menyelidiki dan menentukan sifat-sifat kelas himpunan bebas dari graf dayung kayak, KP_(k,m,l) , sebuah graf yang terbentuk dari dua siklus dengan panjang k dan m yang dihubungkan oleh sebuah lintasan dengan panjang l dalam kaitannya dengan bilangan Fibonacci. Metode yang digunakan adalah analisis kombinatorial terhadap struktur graf dayung kayak untuk menghitung banyaknya himpunan bebasnya. Hasil penelitian menetapkan relasi rekursif untuk banyaknya himpunan bebas, yang dinotasikan i(KP_(k,m,l)). Secara spesifik, i(KP_(k,m,l))  ditunjukkan sebagai jumlah dari i(KP_(k,m,l-1)) dan i(KP_(k,m,l-2)); sifat rekursif serupa juga berlaku untuk panjang siklus k dan m, yang menunjukkan bahwa banyaknya himpunan bebas mengikuti relasi rekursif serupa Fibonacci terhadap setiap parameter.