KAJIAN RAINBOW 2-CONNECTED PADA GRAF EKSPONENSIAL DAN BEBERAPA OPERASI GRAF

Abstract

Salah satu teori yang dikembangkan dalam teori graf adalah rainbow connection. Rainbow connection adalah pewarnaan sisi pada graf G dimana setiap dua titik yang berbeda memiliki minimal satu rainbow path. Jika setiap dua titik yang berbeda di G dihubungkan dengan rainbow path, maka graf G dikatakan rainbow connected. Suatu lintasan u ¡ v di G dikatakan rainbow path jika tidak ada dua sisi di lintasan tersebut yang memiliki warna sama. Pewarnaan sisi yang menyebabkan G bersifat rainbow connected disebut rain- bow coloring. Banyaknya warna minimal yang digunakan agar graf G bersifat rainbow connected disebut rainbow connection number yang dinotasikan de- ngan rc(G). Apabila terdapat minimal 2 rainbow path yang menghubungkan setiap dua titik berbeda di G, maka graf G dikatakan rainbow 2-connected yang dinotasikan dengan rc2(G). Untuk pemberian rainbow coloring harus menggambarkan pola fungsi agar mudah dalam mencari fungsi dari pewar- naannya. Rainbow connection dapat diterapkan pada hasil operasi dari beberapa graf khusus, misalnya graf lintasan (path), graf siklus (cycle), graf lengkap (complete), graf buku segitiga (triangular book), dan graf kincir (windmill ). Operasi graf merupakan cara untuk memperoleh graf baru dengan melakukan operasi terhadap dua graf. Adapun graf hasil operasi yang digunakan dalam penelitian ini antara lain yaitu C4 Btn, C4 Kn, Wd(3;n) C3 , Cn +Wd(3;2), C3¤Kn, Bt3¤Kn, dan Wd(3;2)¤Kn. Penelitian ini menggunakan metode deduktif aksiomatik. Tujuan dari penelitian ini adalah untuk menentukan kardinalitas titik dan sisi, rainbow connection, dan rainbow 2-connected dari graf C4 Btn, C4 Kn, Wd(3;n) C3 , Cn + Wd(3;2), C3¤Kn, Bt3¤Kn, dan Wd(3;2)¤Kn. Pada penelitian ini dihasilkan 7 teorema baru, antara lain: 1. Teorema 4.1.1 Misal G adalah graf eksponensial dari graf siklus dengan graf buku segitiga. Untuk n ¸ 2, rc(C4 Btn) = 3 dan rc2(C4 Btn) = 4. 2. Teorema 4.1.2 Misal G adalah graf eksponensial dari graf siklus dengan graf lengkap. Untuk n ¸ 4, rc(C4 Kn) = 3 dan rc2(C4 Kn) = 4. 3. Teorema 4.1.3 Misal G adalah graf eksponensial dari graf kincir dengan graf siklus. Untuk n ¸ 2, rc(Wd(3;n) C3) = 4 dan rc2 (Wd(3;n) C3) = 5. 4. Teorema 4.1.4 Misal G adalah joint dari graf siklus dengan graf kincir. Untuk n ¸ 3, rc(Cn +Wd(3;2)) = 2 dan rc2(Cn +Wd(3;2)) = 3. 5. Teorema 4.1.5Misal G adalah cartesian product dari graf siklus dengan graf lengkap. Untuk n ¸ 4, rc(C3¤Kn) = 2 dan rc2(C3¤Kn) = 3. 6. Teorema 4.1.6 Misal G adalah cartesian product dari graf buku segitiga dengan graf lengkap. Untuk n ¸ 4, rc(Bt3¤Kn) = 3 dan rc2(Bt3¤Kn) = 4. 7. Teorema 4.1.7 Misal G adalah cartesian product dari graf kincir dengan graf lengkap. Untuk n ¸ 4, rc(Wd(3;2)¤Kn) = 3 dan rc2(Wd(3;2)¤Kn) = 4.