Perpustakaan Digital ITB

Diberikan graf G dan H, notasi F?(G,H) menyatakan bahwa setiap pewarnaan merah-biru pada semua sisi graf F terdapat subgraf G merah atau subgraf H biru. Bilangan Ramsey sisi dari pasangan graf G dan H, dinotasikan r ?(G,H), adalah bilangan bulat positif terkecil k sehingga terdapat graf F dengan k sisi yang memenuhi F?(G,H). Secara umum, graf F dengan banyak sisi minimum yang memenuhi sifat F?(G,H) belum tentu graf terhubung. Untuk kasus F adalah graf terhubung, didefinisikan bilangan Ramsey sisi terhubung pasangan graf (G,H), dinotasikan dengan r ?_c (G,H), sebagai bilangan bulat positif terkecil t sehingga terdapat graf terhubung F dengan t sisi yang memenuhi F?(G,H). Dalam disertasi ini dikaji tentang penentuan bilangan Ramsey sisi terhubung r ?_c (?nK?_2,H), dengan H adalah graf terhubung tertentu yaitu graf bintang, graf lintasan, graf siklus, graf bintang ganda, dan graf sapu. Selain itu, juga dikaji tentang penentuan bilangan Ramsey sisi terhubung r ?_c (?nK?_2,H), dengan H adalah graf tak terhubung tertentu yaitu graf padanan, gabungan graf bintang, dan gabungan graf lintasan. Pada kajian bilangan Ramsey sisi terhubung r ?_c (?nK?_2,H), dengan H adalah graf bintang dan graf lintasan, diperoleh batas atas dari r ?_c (?nK?_2,K_(1,m) ) dan r ?_c (?nK?_2,P_t ) untuk n?2, m?3, dan t?3. Selanjutnya ditunjukkan nilai eksak dari r ?_c (?nK?_2,K_1,3 ) untuk n?2, r ?_c (?nK?_2,K_(1,m) ) untuk n?{2,3} dan m?4, serta r ?_c (?nK?_2,P_t ) untuk t?{3,4,5} dan n?{3,4,5,6}. Untuk pasangan graf (?nK?_2,H), dengan H adalah graf siklus, graf bintang ganda, dan graf sapu, diperoleh batas atas bilangan Ramsey sisi terhubung r ?_c (?2K?_2,C_r ) untuk r?7, r ?_c (?nK?_2,C_4 ) untuk n?4, r ?_c (?2K?_2,S(1,m)) untuk m?3, r ?_c (?2K?_2,S_(m,m) ), dan r ?_c (?3K?_2,S_(m,m) ) untuk m?2. Selain itu, diperoleh juga nilai eksak r ?_c (?nK?_2,C_r ) untuk n?{2,3} dan t?{4,5,6},? r ??_c (?2K?_2,S_(m,m) ) untuk m?{2,3}, dan r ?_c (?2K?_2,S(1,m)) untuk m?3. Pada kajian akhir disertasi, diperoleh juga nilai eksak bilangan Ramsey sisi terhubung r ?_c (?nK?_2,?lK?_2 ), r ?_c (?nK?_2,?2K?_(1,m) ), dan r ?_c (?nK?_2,?2P?_t ) untuk n,l,t?2, m?3. Selain itu, diperoleh juga nilai eksak r ?_c (?nK?_2,?2P?_3 ) untuk n?{3,4,…,8}.