PEWARNAAN SISI r-DINAMIS PADA GRAF KHUSUS SERTA GRAF OPERASI SAKEL DAN GENERALISASINYA

Abstract

Teori graf berkembang semakin luas. Terdapat banyak topik yang menarik untuk dikaji salah satunya adalah pewarnaan. Pewarnaan graf digolongkan menjadi pewarnaan titik (vertex coloring), pewarnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Pada pewarnaan graf, tidak boleh ada warna yang sama saling bertetangga. Dalam hal ini pewarnaan dengan k-warna yang paling mini- mum pada suatu graf disebut sebagai bilangan kromatik yaang dinotasikan dengan (G). Pada pewarnaan graf, tidak boleh ada warna yang sama saling bertetangga. Pengembangan dari k-warna dikembangkan oleh Hong-Jian Lai dan Bruce Mont- gomory pada tahun 2002 yang memperkenalkan konsep pewarnaan dinamis. Pe- warnaan k- warna dinamis pada graf G merupakan pewarnaan titik pada graf G sebanyak k warna sedemikian hingga setiap titik berderajat minimum dua pada graf G setidaknya memiliki dua warna berbeda dengan titik - titik ketetanggaannya. Ni- lai k terkecil dimana graf G memiliki pewarnaan k-warna dinamis disebut sebagai bilangan kromatik dinamis, dinotasikan dengan (G), kemudian digeneralisasikan menjadi pewarnaan titik r-dinamis. Perwarnaan titik r-dinamis kemudian mengalami perkembangan yaitu pe- warnaan sisi r-dinamis yang disesuaikan dengan kondisi atau syarat pada pewar- naan sisi graf. Pewarnaan sisi r-dinamis pada suatu graf G didefinisikan seba- gai pemetaan c dari E(G) ke himpunan warna sedemikian sehingga jC(N(e))j minr; d(u) + d(v) 􀀀 2 untuk setiap e = uv 2 E(G), dimana N(e) merupakan himpunan sisi yang bersisian dengan sisi e, dan d(u) merupakan derajat dari titik u. Penggunakan k-warna dinamis yang paling minimal disebut dengan bilangan kro- matik sisi r-dinamis yang dinotasikan dengan r(G). Pewarnaan sisi r-dinamis dapat diterapkan pada graf khusus maupun graf operasi. Operasi graf adalah metode yang digunakan untuk memperoleh graf baru dengan cara mengkombinasikan dua atau lebih. Adapun graf yang digunakan dalam penelitian ini yaitu TLn; TCLn;BTn; shack(H2;2; v; n); shack(Pr4; e; n); shack (BTn; v; n); shack(W6; v; n), dan shack(Wd3;3; v; n).