Perpustakaan Digital ITB

menentukan benar-salahnya suatu formula logika (Ramsey, 1930). Kemudian, teori ini berkembang dan dikaji berbagai variannya serta perumumannya. Salah satu kajian perumumannya adalah teori graf Ramsey minimal diperkenalkan oleh Burr dkk. (1976). Misalkan graf G dan H merupakan graf sebarang. Notasi F ! (G,H) menyatakan bahwa sebarang pewarnaan merah-biru terhadap semua sisi di F selalu mengakibatkan adanya salinan subgraf G merah atau salinan subgraf H biru di dalam graf F. Kemudian, untuk setiap e di F notasi F ? e 9 (G,H) menyatakan bahwa terdapat pewarnaan merah-biru terhadap sisi-sisi di F ? e, sehingga graf tersebut tidak memuat salinan G merah dan salinan H biru. Kelas R(G,H) menyatakan himpunan graf F yang memenuhi syarat: (i) F ! (G,H) dan (ii) untuk sebarang e 2 F, F ? e 9 (G,H). Pasangan (G,H) disebut Ramsey berhingga jika kelas R(G,H) memiliki berhingga anggota, sedangkan pasangan (G,H) disebut Ramsey tak berhingga jika kelas R(G,H) memiliki tak berhingga anggota. Penelitian pada disertasi ini mengkaji suatu kelas Ramsey tak berhingga R(G,H), dengan G adalah graf siklus dan H adalah graf bintang. Masalah mengenai karakterisasi dan penentuan semua graf Ramsey (G,H)-minimal untuk sebarang graf G dan H bukanlah hal yang sederhana atau mudah untuk dikerjakan, sekalipun graf G dan H yang dipilih adalah graf-graf kecil dan berstruktur sederhana. Akan tetapi, masalah ini tetaplah menjadi hal yang menarik untuk dikaji. Beberapa graf Ramsey minimal anggota kelas R(C3,K1,2), R(C4,K1,2), atau R(C6,K1,2) sudah diperoleh. Namun, secara umum karakterisasi dari kelas R(Cm,K1,n) untuk setiap m $ 3 dan n $ 2 masih menjadi masalah terbuka. Hasil pada disertasi ini dapat dibagi menjadi dua bagian, yaitu graf Ramsey (Cm,K1,2)-minimal untuk m $ 7 dan graf Ramsey (C4,K1,n) untuk n $ 2. Pada bagian pertama, hasil yang diperoleh adalah graf Ramsey (C2m,K1,2) untuk m $ 6 yang dikonstruksi dengan memodifikasi graf Harary, dan graf Ramsey (Cm,K1,2) yang berasal dari suatu kelas graf sirkulan tertentu untuk m $ 7. Untuk m 2 {8, 9, 10} dan m = 4k +3, dengan k bilangan bulat positif, dapat ditunjukkan bahwa kelas graf sirkulan tersebut adalah graf Ramsey (Cm,K1,2)-minimal. Hasil utama pada bagian kedua adalah metode konstruksi graf Ramsey minimal yang dinamakan graf F-theta. Graf F-theta dibangun oleh sebarang graf berbobotsisi F. Diperoleh syarat cukup dan syarat perlu terkait jumlah bobot sisi dari graf F sehingga graf F-theta tersebut merupakan graf Ramsey (C4,K1,n)-minimal. Sebagai tambahan, dapat diturunkan sifat-sifat yang harus dipenuhi oleh distribusi bobot sisi dan bobot titik pada graf F. Bobot titik adalah jumlah dari bobot sisi yang menempel pada titik tersebut. Metode konstruksi yang dijelaskan di atas dikembangkan lebih lanjut dengan memanfaatkan operasi subdivisi pada F. Dengan melakukan subdivisi berulang kali, diperoleh suatu kelas tak berhingga dari graf-theta diR(C4,K1,n) untuk n $ 2. Berdasarkan syarat bobot titik dan sisi yang dimiliki, beberapa barisan bobot sisi untuk graf pohon dan unisiklik juga diberikan untuk mendapatkan pohon-theta dan unisiklik-theta yang merupakan anggota kelas R(C4,K1,n). Hasil lainnya yang diberikan adalah suatu konstruksi kelas graf baru, dinamakan graf H(n), yang merupakan graf Ramsey (C4,K1,n)-minimal untuk setiap n $ 3.