ANALISA NILAI KROMATIK PEWARNAAN TOTAL r−DINAMIS PADA OPERASI COMB PRODUCT DARI GRAF-GRAF KHUSUS

Abstract

Teori graf pertama kali diperkenalkan oleh seorang matematikawan berkebangsaan Swiss bernama Leonhard Euler pada tahun 1736. Salah satu teori yang dikembangkan dalam teori graf adalah pewarnaan graf (coloring). Terdapat tiga macam pewarnaan dalam teori graf, yaitu pewarnaan titik (vertex coloring), pewarnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Selanjutnya, H. Lai dan B. Montgomery memperkenalkan konsep pewarnaan dinamis danmenuangkannyadalamsebuahartikelyangberjudulDynamicColoringofGraphs. Dari penelitian diatas mulai dikembangkan lagi tentang pewarnaan dinamis pada graf. Terdapat tiga macam pewarnaan r−dinamis dalam teori graf yaitu pewarnaan titik r−dinamis, pewarnaan sisi r−dinamis, dan pewarnaan total r−dinamis. Pewarnaan total r-dinamis pada graf G adalah pemetaan c : V (G)∪E(G) ke himpunan warna sedemikian hingga memenuhi kondisi∀v ∈ V (G),|c(N(u))|≥ min{r,d(u) + N(u)} dan ∀e = uv ∈ E(G),|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 χ”r(G). Pewarnaan total r-dinamis dapat diterapkan pada graf khusus maupun graf operasi. Operasi yang digunakan pada penelitian ini yaitu operasi Comb Product. Operasi comb product dari graf L dan H dinotasikan L ◃ H adalah operasi graf yang diperoleh dengan mengambil salinan dari graf L dan |L| salinan dari H dan merekatkan salinan ke-i dari graf H di titik cangkok o pada titik ke-i dari graf L. Adapun graf yang digunakan dalam penelitian ini yaitu graf Pn ◃ Wd3,3, Ln ◃ Pm, Pn ◃F1,3, Ln ◃S3, Pn ◃H2,2, TLn ◃C3 dan Sn ◃C3. Penelitian ini menggunakan metode deduktif dan pendeteksian pola. Tujuan penelitianiniadalahmenentukanhimpunantitikdansisipadagrafoperasidanbilangan kromatikpewarnaantotalr-dinamispadagrafPn◃Wd3,3,Ln◃Pm,Pn◃F1,3,Ln◃S3, Pn ◃ H2,2, TLn ◃ C3 dan Sn ◃ C3 sehingga dihasilkan 7 teorema baru, diantaranya adalah Penelitian ini dikategorikan sebagai penelitian eksploratif dan menggunakan metode pendeteksian pola. Tujuan penelitian ini adalah menentukan nilai kromatik total dari beberapa graf khusus dan dihasilkan 7 teorema baru, diantaranya adalah: 1. Teorema4.1Misalkan G adalah graf Pn ◃Wd3,3 dimana n ≥ 3 dan titik z sebagai titik cangkok pada graf Wd3,3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) =                            9,untuk 1 ≤ r ≤ 7 10,untuk r = 8 12,untuk 9 ≤ r ≤ 10 r + 2,untuk 11 ≤ r ≤ 13 16,untuk 14 ≤ r ≤ 15 17,untuk r ≥ 16 2. Teorema 4.2 Misalkan G adalah graf Ln ◃ Pm dimana n ≥ 2, m ≥ 3 dan titik y1 sebagai titik cangkok pada graf Pm. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) = 5,untuk 1 ≤ r ≤ 3 8,untuk r = 4 10,untuk r = 5 13,untuk 6 ≤ r ≤ 7 15,untuk r ≥ 8 3. Teorema 4.3 Misalkan G adalah graf Pn ◃F1,3 dimana n ≥ 3 dan titik y3 sebagai titikcangkokpadagrafF1,3. Bilangankromatikpewarnaantotalr-dinamispadagraf G adalah χ”r(G) = 5,untuk 1 ≤ r ≤ 3 6,untuk r = 4 8,untuk r = 5 10,untuk 6 ≤ r ≤ 7 11,untuk r ≥ 8 4. Teorema 4.4 Misalkan G adalah graf Ln ◃ S3 dimana n ≥ 2 dan titik z3 sebagai titik cangkok pada graf S3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) =

5,untuk 1 ≤ r ≤ 3 6,untuk r = 4 8,untuk r = 5 10,untuk r = 6 12,untuk r = 7 dan r ≥ 8 5. Teorema 4.5 Misalkan G adalah graf TLn ◃C3 dimana n ≥ 3 dan titik y3 sebagai titik cangkok pada graf C3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) =                                  7,untuk 1 ≤ r ≤ 4 8,untuk 5 ≤ r ≤ 6 9,untuk r = 7 r + 3,untuk 8 ≤ r ≤ 9 15,untuk r = 10 18,untuk r = 11 20,untuk r ≥ 12 6. Teorema 4.6 Misalkan G adalah graf Pn ◃H2,2 dimana n ≥ 3 dan titik y4 sebagai ix titik cangkok pada graf H2,2. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) =

5,untuk 1 ≤ r ≤ 3 8,untuk r = 4 9,untuk 5 ≤ r ≤ 7 10,untuk r ≥ 8 7. Teorema 4.7 Misalkan G adalah graf Sn ◃ C3 dimana n ≥ 4 dan titik z3 sebagai titik cangkok pada graf C3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah χ”r(G) =

n + 3,untuk 1 ≤ r ≤ n + 2 n + 4,untuk r = n + 3 n + 6,untuk n + 4 ≤ r ≤ n + 5 r + 1,untuk n + 6 ≤ r ≤ 2n + 3 2n + 5,untuk r ≥ 2n + 4