ANALISIS PEWARNAAN TITIK DAN SISI r-DINAMIS PADA GRAF HASIL OPERASI COMB SISI Cn H

Abstract

Pewarnaan merupakan salah satu topik penelitian yang banyak diminati dalam teori graf. Pewarnaan graf, merupakan kasus khusus dari pelabelan graf yang memiliki tiga macam aspek yaitu pewarnaan titik (vertex coloring ), pe- warnaan sisi (edge coloring ), dan pewarnaan wilayah (region coloring ). Pewar- naan r-dinamis merupakan pengembangan dari pewarnaan k-warna dinamis yang diperkenalkan oleh Montgomery pada tahun 2002. Pewarnaan k-warna dinamis pada graf G merupakan pewarnaan titik pada graf G sebanyak k warna sedemikian hingga setiap titik berderajat minimum dua pada G setidaknya memiliki dua warna berbeda dengan titik-titik ketetanggaannya. Nilai k terkecil dimana graf G memiliki pewarnaan k-warna dinamis disebut sebagai bilangan kromatik dinamis, disimbolkan dengan χ(G). Penelitian ini meneliti tentang pewarnaan titik r-dinamis pada graf hasil operasi comb sisi serta pengembangannya pada pewarnaan sisi r-dinamis. Graf hasil operasi comb sisi yaitu salah satu operasi graf yang menerapkan definisi perpangkatan. Graf hasil operasi comb sisi dapat diartikan dengan menempelkan sisi pada suatu graf dengan salah satu sisi pada graf lain yang dilambangkan dengan G H, dimana G dan H merupakan sebarang graf. Adapun graf-graf khusus yang dimaksud dalam pewarnaan r-dinamis diantaranya adalah graf lin- tasan (path), graf lingkaran (cycle), graf buku segitiga (triangular book), dan graf bintang (star). Hasil penelitian ini adalah pewarnaan titik r-dinamis dan pe- warnaan sisi r-dinamis dari hasil operasi comb sisi graf G H dengan graf G merupakan graf lingkaran dan graf H merupakan semua graf khusus. Metode yang digunakan dalam penelitian ini adalah metode deduktif ak- siomatik, yang diawali dengan istilah yang tidak didefinisikan dan istilah yang didefinisikan, kemudian dapat disusun pernyataan pangkal yang biasa disebut

aksioma atau postulat. Setelah itu, disusun teorema-teorema ataupun definisi- definisi. Adapun teorema yang disusun harus dibuktikan melalui proses deduktif sehingga kebenarannya berlaku secara umum dalam ruang lingkupnya. Hasil penelitian ini berupa teorema baru mengenai pewarnaan titik r-dinamis dan pewarnaan sisi r-dinamis pada graf hasil operasi comb sisi Cn H. Dari penelitian ini didapatkan Observasi, Teorema, Lemma, dan Dugaan yang di- hasilkan sebagai berikut: a. Misalkan G merupakan graf Cn H, maka ∆(G) ≥ ∆(H). Yang telah dibuktikan pada Observasi 4.1.1; b. Misalkan G merupakan graf Cn H, maka ∆(G) ≥ ∆(H) + 1. Yang telah dibuktikan pada Observasi 4.1.2; c. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 3 dan sisi y1y2

sebagai sisi cangkok pada graf Pm. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Pm dapat ditulis sebagai berikut:



χr (Cn Pm) = 

3 ; 1 ≤ r ≤ 2

4 ; r ≥ 3 5 ; r ≥ 3 dan n ≡ 0(mod 5)

yang telah dibuktikan pada Teorema 4.1.1;

d. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 4 dan sisi yiyi+1 sebagai sisi cangkok pada graf Pm dengan 2 ≤ i ≤ m−1. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Pm dapat ditulis sebagai berikut:



χr (Cn Pm) = 

3 ; 1 ≤ r ≤ 2 4 ; r = 3

5 ; r ≥ 4

yang telah dibuktikan pada Teorema 4.1.2;

e. Misalkan G merupakan graf Cn Cm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Cm. Bilangan kromatik r-dinamis pewarnaan titik pada

Cn Cm dapat ditulis sebagai berikut: 

χr (Cn Cm) = 

3 ; 1 ≤ r ≤ 2 4 ; r = 3

5 ; r ≥ 3

yang telah dibuktikan pada Teorema 4.1.3;

f. Misalkan G merupakan graf Cn Sm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Sm. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Sm dapat ditulis sebagai berikut:



χr (Cn Sm) = 

3 ; 1 ≤ r ≤ δ + 1

r + 1 ; δ + 2 ≤ r ≤ ∆ ∆ + 1 ; r ≥ ∆

yang telah dibuktikan pada Teorema 4.1.4;

f. Misalkan G merupakan graf Cn Amal(C3, P2, m) untuk n ≥ 3 dimana sisi cangkok p2 pada m. Bilangan kromatik r-dinamis pewarnaan titik pada Cn Amal(C3, P2, m) dapat ditulis sebagai berikut:



χr (Cn Amal(C3, P2, m)) = 

3 ; 1 ≤ r ≤ δ r + 1 ; δ + 1 ≤ r ≤ ∆ − 1

∆ + 1 ; r ≥ ∆

yang telah dibuktikan pada Teorema 4.1.5;

g. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 3 dan sisi y1y2

sebagai sisi cangkok pada graf Pm. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Pm dapat ditulis sebagai berikut:



λr = 

3 ; untuk 1 ≤ r ≤ 2 5 ; untuk n ≡ 0(mod 5), r ≥ 3 6 ; untuk n /= 0(mod 5), r ≥ 3

yang telah dibuktikan pada Teorema 4.2.1;

h. Misalkan G merupakan graf Cn Pm untuk n ≥ 3, m ≥ 4 dan sisi yiyi+1 sebagai sisi cangkok pada graf Pm dengan 2 ≤ i ≤ m−1. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Pm dapat ditulis sebagai berikut:

 

λr =  

4 ; untuk 1 ≤ r ≤ 3 5 ; untuk r = 4

8 ; untuk i = genap, r ≥ 5 9 ; untuk i = ganjil, r ≥ 5

yang telah dibuktikan pada Teorema 4.2.2;

i. Misalkan G merupakan graf Cn Cm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Cm. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Cm dapat ditulis sebagai berikut:

     

λr =      

4 ; untuk 1 ≤ r ≤ 3

6 ; m /= 4 untuk semua n dan m /= 5 untuk n ≡ 1(mod 3); 4 ≤ r ≤ 5 7 ; m = 4 untuk semua n dan m = 5 untuk n ≡ 1(mod 3); 4 ≤ r ≤ 5 8 ; n ≡ 1(mod 3) dan n ≡ 2(mod 3); r ≥ 6 9 ; n ≡ 0(mod 3); r ≥ 6

yang telah dibuktikan pada Teorema 4.2.3;

j. Misalkan G merupakan graf Cn Sm untuk n ≥ 3 dan m ≥ 3 dan sisi cangkok pada graf Sm. Bilangan kromatik r-dinamis pewarnaan sisi pada Cn Sm dapat ditulis sebagai berikut:



λr = 

∆ ; 1 ≤ r ≤ ∆ − 1 2∆ ; ∆ ≤ r ≤ ∆ + 2

2∆ + 1 ; r ≥ ∆ + 3