| dc.description.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 | en_US |
