Perpustakaan Digital ITB

Bilangan Ramsey R(a, b) untuk bilangan asli a, b ? 2 didefinisikan sebagai bilangan bulat terkecil r sedemikian sehingga setiap pewarnaan-2 pada graf lengkap Kr memuat subgraf monokromatik Ka atau Kb. Karena kompleksitas dalam menentukan nilai eksak bilangan Ramsey klasik, para peneliti memperkenalkan konsep bilangan Ramsey graf untuk graf sebarang. Diberikan dua graf sederhana G dan H, bilangan Ramsey R(G,H) adalah bilangan bulat terkecil r sedemikian sehingga setiap graf F berorde r memenuhi kondisi F ? G atau F ? H. Batas bawah bilangan Ramsey telah ditetapkan menggunakan bilangan kromatik ?(H) dan surplus kromatik s(H), yaitu R(G,H) ? (?(H) ? 1)(n ? 1) + s(H). Penelitian ini memfokuskan kajian pada penentuan bilangan Ramsey R(Tn,H) untuk pohon Tn berorde n versus graf H yang memuat titik dominasi, yaitu titik yang bertetangga dengan seluruh titik lainnya. Kelas graf H ini meliputi graf roda Wn, graf kipas F1,n, dan graf kupu-kupu diperumum B(k, n ? k). Meskipun nilai bilangan Ramsey untuk graf pohon yang berbentuk bintang versus graf roda berorde kecil telah diketahui, akan tetapi untuk graf pohon secara umum versus graf roda atau graf dengan titik dominasi lainnya seperti graf kipas dan graf kupu-kupu diperumum masih menjadi permasalahan. Dalam studi ini, kami telah menentukan nilai eksak R(Tn,H) di mana H merupakan graf kipas atau graf kupu-kupu diperumum dengan orde tertentu, khususnya dengan meninjau pohon Tn yang memiliki derajat maksimum tertentu. Lebih lanjut, pekerjaan ini telah menetapkan batas bawah yang lebih ketat untuk bilangan Ramsey graf pohon terhadap graf roda, R(Tn,Wm), dan graf pohon terhadap graf kipas, R(Tn, F1,m), untuk nilai m dan n tertentu. Selain itu, pada penelitian ini juga telah diturunkan hubungan antara R(G1,H) dan R(G2,H) untuk suatu graf G1,G2, dan H apabila G1 dan G2 memenuhi kondisi tertentu berdasarkan keterkandungan atau derajat maksimum dari G1 dan G2. Hasil-hasil ini berkontribusi pada teori Ramsey dalam hal menambahkan nilai eksak bilangan Ramsey yang diketahui, mempertajam batas bawah bilangan Ramsey untuk graf roda dan graf kipas tertentu, serta mengetahui hubungan antara dua bilangan Ramsey yang memenuhi kondisi tersebut di atas.