BILANGAN RAMSEY PADA GRAF BINTANG Sn DAN GRAF RODA BERKEPALA DUA = RAMSEY NUMBER ON THE STAR GRAPH Sn AND THE TWO-HEADED WHEEL GRAPH W2,m

ALIFIA NURUL KHAIRIYAH. Bilangan Ramsey pada Graf Bintang dan Graf Roda Berkepala Dua (dibimbing oleh Prof. Dr. Hasmawati, M.Si.). Latar Belakang. Banyak penelitian sebelumnya yang telah mengkaji bilangan Ramsey untuk graf lengkap, graf bintang, maupun graf roda namun untuk bilangan Ramsey pada graf bintang dan graf roda berkepala dua belum diketahui. Tujuan. Penelitian ini bertujuan untuk menentukan bilangan Ramsey pada graf bintang S_n untuk n=3,4,5 dan graf roda berkepala dua W_(2,m) untuk m≥3. Metode. Penelitian ini dibagi menjadi beberapa tahap, yaitu menentukan batas bawah menurut Chvátal dan Harary mulai dari orde terkecil, kemudian menentukan dan membuktikan batas bawah dan batas atas dari graf yang telah ditentukan, apabila batas bawah dan batas atas telah sama maka dapat ditentukan dan dibuktikan teorema bilangan Ramsey R(S_n,W_(2,m)) untuk n=3,4,5 dan m≥3 dengan n,m adalah bilangan asli. Hasil. Bilangan Ramsey R(S_(3,) W_(2,m) )={█(7,m=3@m+2,m≥4 )┤, R(S_(4,) W_(2,m) )={█(10, 3≤m≤5@m+4,m≥6 )┤, dan R(S_(5,) W_(2,m) )=m+6 untuk m≥8 dengan m bilangan asli. Kesimpulan. Merujuk pada hasil dan dengan adanya konsep variasi graf roda berkepala dua, diperoleh hasil yang sama untuk bilangan Ramsey graf bintang dan graf roda pada R(S_(n,) W_m )=R(S_(n,) W_(2,m) )=3n-2 untuk n=3 dan m=2n-1, yaitu R(S_(3,) W_5 )=R(S_(3,) W_2,5 )=7. Namun untuk R(S_(4,) W_7 ) dan R(S_(4,) W_2,7 ) memiliki hasil yang berbeda yaitu R(S_(4,) W_2,7 )= R(S_(4,) W_7 )+1. Begitu juga dengan (S_(5,) W_9 ) dan R(S_(5,) W_2,9 ) yang memiliki hasil yang berbeda yaitu R(S_(5,) W_2,9 )=R(S_(5,) W_9 )+2.

Kata kunci : bilangan Ramsey, teorema Bondy, graf bintang, graf roda, graf roda berkepala dua