Perpustakaan Digital ITB

Seorang ilmuwan bernama Frank Plumpton Ramsey mengemukakan suatu teori mengenai pencarian prosedur untuk menemukan benar-salahnya suatu formula logika yang diberikan, teori tersebut dikenal sebagai Teori Ramsey [24]. Kemudian, teori Ramsey berkembang hingga ditemukannya teori graf Ramsey minimal oleh Burr pada tahun 1970. Menurut Burr [7], teori graf Ramsey minimal didefinisikan sebagai berikut. Misalkan graf G dan graf H merupakan graf sederhana sebarang, yaitu graf yang tidak memuat sisi ganda dan loop. Notasi F ! (G,H) berarti bahwa sebarang pewarnaan merah-biru terhadap semua sisi di graf F selalu menyebabkan salinan subgraf G merah atau salinan subgraf H biru termuat di dalam graf F. Kemudian, 8e 2 F notasi F ? e 9 (G,H) menyatakan bahwa terdapat pewarnaan terhadap sisi-sisi F ? e sehingga graf tersebut tidak memuat salinan G merah dan salinan H biru. Kelas R(G,H) menyatakan himpunan graf yang memenuhi syarat: 1. F ! (G,H) dan 2. 8e 2 F, F ? e 9 (G,H). Pasangan (G,H) disebut Ramsey hingga jika kelas R(G,H)memiliki anggota berhingga, sedangkan pasangan (G,H) disebut Ramsey tak hingga jika kelas R(G,H) memiliki anggota tak berhingga. Dalam tesis ini akan dibahas graf yang termasuk ke dalam kelas R(G,H) dengan graf G suatu graf siklus dan graf H suatu 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. Diperoleh beberapa graf anggota kelas khusus kelas Ramsey (Cn,K1,2)-minimal untuk n 2 [5, 9] i dan kelas Ramsey (C4,K1,m)-minimal untuk m % 3. Kemudian sudah diperoleh karakterisasi graf Ramsey untuk pasangan (C2n,K1,2) untuk n % 7 ganjil.