Analisis Pewarnaan Total r-Dinamis pada Graf Hasil Operasi Comb Sisi

Abstract

Pewarnaan graf adalah memberikan warna pada objek tertentu pada graf. Objek tersebut dapat berupa titik, sisi, maupun wilayah. Pewarnaan k−warna dinamis pada suatu graf G adalah pewarnaan titik sebanyak k warna dimana titik yang berderajat minimum 2 memiliki dua warna yang berbeda dengan titik ketetenggannya. Nilai k warna dinamis yang digunakan disebut dengan bilangan kromatis dinamis dan disimbolkan dengan χ . Pewarnaan titik k−warna dinamis kemudian digeneralisasikan menjadi r pewarnaan titik r−dinamis dan mengalami perkembangan yaitu menjadi pewarnaan sisi r−dinamis. Kemudian dari pewarnaan titik r−dinamis dan pewarnaan sisi r−dinamis kembali mengalami perkembangan yaitu menjadi pewarnaan total r−dinamis yang telah disesuaikan dengan kondisi atau syarat pada pewarnaan total r−dinamis. Pewarnaan total r-dinamis pada graf G adalah pemetaan c : V (G) S E(G) ke himpunan warna sedemikian hingga memenuhi kondisi |c(N(u))| ≥ min{r, d(u) + N(u)} dan |c(N(e))| ≥ min{r, d(u)+ d(v)}. Bilangan kromatik dari pewarnaan total r-dinamis adalah banyaknya nilai k minimum yang dibutuhkan untuk mewarnai graf G, dan dinotasikan dengan χ (G). Pewarnaan total r-dinamis didapat pada beberapa graf hasil operasi comb sisi diantaranya adalah P n D C m , P n D W m , P n D F m , S n D C m ′′ r , S . Penelitian ini dikategorikan sebagai penelitian eksploratif dan menggunakan metode pendeteksian pola. Tujuan penelitian ini adalah menentukan nilai kromatik total dari beberapa graf hasil operasi comb sisi, graf hasil operasi comb sisi dapat diartikan dengan mencangkokkan salah satu sisi graf H pada setiap sisi graf G. Graf hasil operasi comb sisi disimbolkan dengan G D H, dimana G dan H merupakan sebarang graf.Dihasilkan enam teorema dan dua lemma baru, diantaranya adalah: 1. Teorema 4.1.1 Misalkan G adalah graf P untuk n ≥ 3, m ≥ 3 dan sisi x 1 x 2 sebagai sisi cangkok pada graf C m n D C m . Bilangan kromatik dinamis pewarnaan total r−dinamis pada G adalah χ ′′ r (P n D C m ) =          5; untuk 1 ≤ r ≤ δ + 1 2∆; untuk δ + 2 ≤ r ≤ 2∆ − 1 2∆ + 1, untuk r ≥ 2∆ 2. Teorema 4.1.2 Misalkan G adalah graf P untuk n ≥ 3, m ≥ 3 dan sisi x 1 x 2 sebagai sisi cangkok pada graf W m n D W m . Bilangan kromatik dinamis pewarnaan total r−dinamis pada G adalah χ ′′ r (P n D W m ) =          ∆ + 1; untuk 1 ≤ r ≤ δ + 1 r + 3; untuk δ + 2 ≤ r ≤ 2∆ − 2 2∆ + 1; untuk r ≥ 2∆ − 1 3. Teorema 4.1.3 Misalkan G adalah graf P untuk n ≥ 3, m ≥ 3 dan sisi Ax 1 sebagai sisi cangkok pada graf F m n D F m . Bilangan kromatik dinamis pewarnaan total r−dinamis pada G adalah χ ′′ r (P n D F m ) =          ∆ + 1; untuk 1 ≤ r ≤ δ + 1 r + m; untuk δ + 2 ≤ r ≤ 2∆ − 2 2∆ + 1; untuk r ≥ 2∆ − 1 4. Teorema 4.1.4 Misalkan G adalah graf S untuk n ≥ 3, m ≥ 3 dan sisi x 1 x 2 sebagai sisi cangkok pada graf C m n D C m . Bilangan kromatik dinamis pewarnaantotal r−dinamis pada G adalah χ ′′ r (S n D C m ) =          ∆ + 1; untuk 1 ≤ r ≤ δ + 1 r + 1; untuk δ + 2 ≤ r ≤ 2∆ − 1 2∆ + 1; untuk r ≥ 2∆ Teorema 4.1.5 Misalkan G adalah graf S untuk n ≥ 3, m ≥ 3 dan sisi Ax 1 sebagai sisi cangkok pada graf S m n D S m . Bilangan kromatik dinamis pewarnaan total r−dinamis pada G adalah χ ′′ r (S n D S m ) =          ∆ + 1; untuk 1 ≤ r ≤ ∆ r + 1; untuk ∆ + 1 ≤ r ≤ 2∆ − 1 2∆ + 1; untuk r ≥ 2∆ Teorema 4.1.6 Misalkan G adalah graf S untuk n ≥ 3, m ≥ 2 dan sisi x 1 x 2 sebagai sisi cangkok pada graf P m n D P m . Bilangan kromatik dinamis pewarnaan total r−dinamis pada G adalah χ ′′ r (S n D P m ) =          ∆ + 1; untuk 1 ≤ r ≤ δ + 2 r + 1; untuk δ + 3 ≤ r ≤ 2∆ − 1 2∆ + 1; untuk r ≥ 2∆ Lemma 4.1.1 Misalkan G adalah graf P n dinamis pewarnaan total r−dinamis pada G adalah χ ′′ r (P Lemma 4.1.2 Misalkan G adalah graf S n DH dimana n ≥ 3. Bilangan kromatik D H) ≤ 2∆ + 1 DH dimana n ≥ 3. Bilangan kromatik dinamis pewarnaan total r−dinamis pada G adalah χ ′′ r (S n n D H) ≤ 2∆ + 1