Abstract

On r-Dynamic Coloring for Graph Operation of Cycle, Star, Complete, and Path Desy Tri Puspasari1 , Dafik2 , Slamin3 1 CGANT- University of Jember 2 Department of Mathematics Education - University of Jember 3 Department of Information System - University of Jember [email protected]; [email protected]; [email protected]

Abstract For integer k, r > 0, (k, r) -coloring of graph G is a proper coloring on the vertices of G by k-colors such that every vertex v of degree d(v) is adjacent to vertices with at least min{d(v), r} different color. By a proper k -coloring of graph G, we mean a map c : V (G) → S, where |S| = k, such that any two adjacent vertices are different color. An r -dynamic k -coloring is a proper k -coloring c of G such that |c(N (v))| ≥ min{r, d(v)} for each vertex v in V (G), where N (v) is the neighborhood of v and c(S) = {c(v) : v ∈ S} for a vertex subset S . The r-dynamic chromatic number, written as χr (G), is the minimum k such that G has an r-dynamic k-coloring. Note the 1-dynamic chromatic number of graph is equal to its chromatic number, denoted by χ(G), and the 2-dynamic chromatic number of graph denoted by χd (G). By simple observation with a greedy coloring algorithm, it is easy to see that χr (G) ≤ χr+1 (G), however χr+1 (G) − χr (G) does not always have the same difference. Thus finding an exact values of χr (G) is significantly useful. In this paper, we investigate the some exact value of χr (G) when G is for an operation product of cycle, star, complete, and path graphs. Keywords: r-dynamic coloring, r-dynamic chromatic number, graph operations.

Pendahuluan Teori graf banyak digunakan sebagai alat bantu untuk menggambarkan suatu persoalan agar lebih mudah dimengerti dan diselesaikan permasalahannya. Teori graf pertama kali diperkenalkan oleh Leonhard Euler, seorang matematikawan berkebangsaan Swiss pada tahun 1736 melalui tulisannya yang berisi upaya pemecahan masalah jembatan Konigsberg yang sangat sulit dipecahkan pada masa itu. Salah satu pokok bahasan yang dikembangkan dalam teori graf adalah pewarnaan (colouring). Permasalahan mendasar dalam pewarnaan graf ini adalah menentukan warna minimal yang dibutuhkan untuk mewarnai sebarang graf yang kemudian disebut dengan chromatic number. Vizing (1964) telah menunjukkan bahwa sebarang graf dapat diwarnai dengan warna maksimal adalah ∆(G) + 1, dimana ∆(G) adalah derajad maksimum sebuah graf. Pewarnaan graf merupakan bidang kajian yang sangat menarik dalam graf, kajiannya terutama ditujukan pada pewarnaan graf-graf khusus seperti graf lengkap, graf lingkaran, graf petersen dan generalisasinya, graf prisma dan anti prisma, graf buku segi-n, graf jejaring dan termasuk graf operasi seperti joint, cartesian product, tensor product, crown product, dan composition[1]. Bahkan perkem-

Desy, et.al: On r-Dynamic Coloring for Graph Operation

2

bangan terkini kajian ini diperluas menjadi r − dynamyc colouring. Misalkan G = (V, E) adalah sebuah graf yang sederhana, terhubung, dan tidak berarah dengan himpunan titik V dan himpunan sisi E, serta d(v) adalah derajat dari setiap titik v di V (G). Derajat maksimum dan minimum dari graf G masing-masing dinotasikan dengan ∆(G) dan δ(G). Untuk bilangan bulat k, r > 0; (k, r) pewarnaan graf G adalah pewarnaan yang tepat pada setiap titik dari graf G dengan k warna sehingga setiap titik v dengan derajat d(v) setidaknya min{d(v), r} warna yang berbeda dengan titik yang bersisihan [7]. Dengan k pewarnaan dari graf G, kita memetakan c : V (G) ⇒ S, dimana |S| = k, sehingga setiap dua simpul yang berdekatan memiliki warna yang berbeda. Sebuah r-dinamis dengan memberi k warna pada graf G sehingga |c(N (v))| ≥ min{r, d(v)} untuk setiap titik v di V (G), dimana N (v) adalah lingkungan v dan c(S) = {c(v) : v ∈ S} untuk setiap titik bagian dari S [2, 5]. Bilangan kromatik r-dinamis, dituliskan dengan χr (G) adalah nilai minimum k sehingga graf G memiliki r-dinamis dengan k-warna. Perhatikan bahwa bilangan kromatik 1dinamis dari sebuah graf adalah sama dengan jumlah warna graf itu sendiri, dan dilambangkan dengan χ(G), dan bilangan kromatik 2-dinamis diperkenalkan oleh M ontgomery dengan nama bilangan kromatik dinamis yang dinotasikan dengan χd (G). Dia mengatakan χ2 (G) ≤ χ(G) + 2 ketika G adalah graf sederhana. Akbari membuktikan spekulasi Montgomery untuk graf bipartit sederhana. Lai, Montgomery, dan Poon membuktikan χ2 (G) ≤ ∆(G) + 1 ketika ∆(G) ≥ 3 dan tidak ada unsur 5-siklus C5 . Kim membuktikan χd (G) ≤ 4 untuk graf planar G dengan ketebalan minimal 7, dan χd (G) ≤ k ketika k ≥ 4 dan tingkat rata4k rata G memiliki nilai maksimum k+2 . Kim membuktikan χ2 (G) ≤ 4 saat G adalah planar dan tidak ada unsur C5 dan juga χd ≤ 5 setiap kali graf G adalah planar[4, 6, 5]. Jelas, χ(G) ≤ χ2 (G), tapi itu ditunjukkan bahwa perbedaan antara jumlah kromatik dan dinamis bilangan kromatik bisa berbeda. Namun, itu menduga bahwa untuk graf biasa perbedaannya adalah paling banyak 2. Hal tersebu terbukti pada [6], jika G adalah bipartit sebuah k grafik biasa, k ≥ 3 dan n < 2k , maka χ2 ≤ 4. Beberapa sifat pewarnaan dinamis dipelajari di [3, 4, 6]. Hal itu terbukti di [?], untuk graf terhubung G, jika ∆(G) ≤ 3, maka χ2 (G) ≤ 4 kecuali G = C5 , dalam hal ini χ2 (C5 ) = 5 dan jika ∆(G) ≥ 4 maka χ(G) ≤ ∆(G) + 1.

Lemma yang Digunakan Berikut ini adalah lemma yang digunakan untuk menentukan pewarnaan dinamik dari sebuah graf. Lemma ini mengkarakteristikan istilah batas atas dari diameter


3

sebuah graf. 3 Teorema 1 [7] Jika diam(G) = 2, maka χ2 (G) ≤ χ(G) + 2, jika dan hanya jika ketika G adalah graf bipartit lengkap atau C5 . 3 Teorema 2 [7] Jika G adalah sebuah k-bilangan kromatik graf dengan diameter paling banyak 3, maka χ2 (G) ≤ 3k, dan batas ini berlaku ketika k ≥ 2. 3 Teorema 3 [11] Jika G adalah sebuah graf khusus dengan p titik dan q sisi dan G mempunyai bilangan kromatik χ maka hubungannya (χ − 1)p ≤ 2q Derajat maksimum dari sebuah graf r-dynamic berlaku sebagai berikut: Observation 1 [7] χr (G) ≥ min{∆(G), r} + 1, dan ini berlaku jika ∆(G) ≤ r maka χr (G) = min{∆(G), r}. 3 Teorema 4 [7] χr (G) ≤ r∆(G)+1, untuk r ≥ 2 jika dan hanya jika G adalah r-regular dengan diameter 2 dan ketebalan 5. Misalkan G2 mendefinisikan sebuah graf yang diperoleh dari G dengan menambahkan sisi dan gabungan titik yang tidak bersisihan, maka r − dynamic dari sebuah graf terbukti sebagai berikut. Observation 2 labelbbb[7] χ(G) ≤ χd (G) ≤ χ3 (G) ≤ · · · ≤ χ∆(G) (G) = χ(G2 ). Hasil operasi cartesian product pada sebuah graf, berlaku sebagai berikut: 3 Teorema 5 [7] If δ(G) ≥ r maka χr (G2H) = max{χ(G), χ(H)}.

Hasil Penelitian Berikut ini adalah hasil pewarnaan r-dynamic vertex coloring untuk beberapa operasi dari graf khusus. Selain menunjukkan bilangan kromatik r-dynamic vertex coloring, peneliti juga menyertakan hasil pewarnaan titik c(v ∈ V (G)) dari graf tersebut. Beberapa graf dan operasi yang digunakan dalam artikel ini adalah (Cn +Cm ), (Sn +Pm ), (Cn ⊙Cm ), (Cn ⊗Cm ), (Cn 2Cm ), (Sn 2Pm ), (Cn [Cm ]), amal(Cn , v, r), amal(Cn + Pm , v, r), shack(Cn + Pm , v, r) 3 Teorema 6 Jika G= (Cn +Cm ). Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan titik dinamis G adalah

4

Desy, et.al: On r-Dynamic Coloring for Graph Operation Untuk n genap χ(G) = χd (G) = χ3 (G) =

(

4, untuk m genap 3 2 5, untuk m = 4k −21k3 +41k−9 , kǫN

χ(G) = χd (G) = χ3 (G) = χ4 (G) = 5, untuk m = 6k − 3, kǫN Untuk n ganjil χ(G) = χd (G) = χ3 (G) = χ4 (G) = 6, untuk m =

4k 3 −21k 2 +41k−9 , kǫN 3

χ(G) = χd (G) = χ3 (G) = χ4 (G) = χ5 (G) = 6, untuk n dan m = 6k − 3, kǫN Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf (Cn + Cm ) bahwa |V | = p = n + m dan |E| = q = nm + n + m, maka batas atas dari bilangan kromatik adalah χ(Cn + Cm ) ≤ ( 2nm+3n+3m ). Fungsi pewarnaan titik pada graf G = (Cn + Cm ) adalah n+m Untuk n genap  (   3, 1 ≤ j ≤ m − 2, j ganjil 1, 1 ≤ i ≤ n − 1, i ganjil c(yj ) = c(xi ) = 4, 1 ≤ j ≤ m − 1, j genap  2, 1 ≤ i ≤ n, i genap  5, j = m Untuk n ganjil    1, 1 ≤ i ≤ n − 2, i ganjil c(xi ) = 2, 1 ≤ i ≤ n − 1, i genap   3, i = n

   4, 1 ≤ j ≤ m − 2, j ganjil c(yj ) = 5, 1 ≤ j ≤ m − 1, j genap   6, j = m

Sehingga terbukti bahwa graf G= (Cn +Cm ) mempunyai bilangan kromatik pewarnaan titik dinamis untuk untuk n genap maka χ(G) = χd (G) = χ3 (G)= 4 3 2 ketika m genap, χ(G) = χd (G) = χ3 (G)= 5 ketika m = ( 4k −21k3 +41k−9 ), kǫN , dan χ(G) = χd (G) = χ3 (G) = χ4 (G)= 5 ketika m = 6k −3, kǫN . Untuk n ganjil, 3 2 maka χ(G) = χd (G) = χ3 (G) = χ4 (G)= 6 ketika m = ( 4k −21k3 +41k−9 ), kǫN , dan χ(G) = χd (G) = χ3 (G) = χ4 (G) = χ5 (G)= 6 ketika n dan m = 6k − 3, kǫN . 2 Open Problem 1 Misalkan G adalah joint Cn dan Cm . Untuk n ≥ 3 dan m ≥ 3, tentukan bilangan kromatik r-dynamic dari graf G untuk r ≥ 4. 3 Teorema 7 Jika G= (Sn + Pm ). Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G adalah χ(G) = χd (G) = χ3 (G) =

4, untuk n m genap ganjil


5

Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf (Sn + Pm ) bahwa |V | = p = n + m + 1 dan |E| = q = nm + n + 2m − 1, maka batas atas dari bilangan kromatik adalah χ(Sn + Pm ) ≤ ( 2nm+3n+5m−1 ). Fungsi pewarnaan titik pada graf G= (Sn + Pm ) adalah n+m+1 c(A) = 3 Untuk n m ganjil genap c(xi ) =

4, 1 ≤ i ≤ n .

c(yj ) =

(

1, 1 ≤ j ≤ m, j ganjil 2, 1 ≤ j ≤ m, j genap

Sehingga terbukti bahwa graf G = (Sn + Pm ) mempunyai bilangan kromatik dan pewarnaan titik dinamis χ(G) = χd (G) = χ3 (G)= 4 untuk n ganjil atau genap pada saat m ganjil atau genap. 2 Open Problem 2 Misalkan G adalah hasil joint dari Sn dan Pm . Untuk n ≥ 3 dan m ≥ 2, tentukan bilangan kromatik r-dynamic dari graf G ketika r ≥ 4. 3 Teorema 8 Jika G= (Cn ⊙ Cm ). Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik pewarnaan titik dinamis G adalah Untuk n genap atau ganjil ( 3, untuk m genap χ(G) = χd (G) = 3 2 4, untuk m = 4k −21k3 +41k−9 , kǫN χ(G) = χd (G) = χ3 (G) = 4, untuk m = 6k − 3, kǫN Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf (Sn + Pm ) bahwa |V | = p = nm + n dan |E| = q = 2nm+n maka batas atas dari bilangan kromatik adalah χ(Cn ⊙Cm ) ≤ ( 5nm+3n nm+n ). Fungsi pewarnaan titik pada graf G = (Cn ⊙ Cm ) adalah Untuk n genap atau ganjil    1, 1 ≤ i ≤ n − 1, i ganjil c(xi ) = 2, 1 ≤ i ≤ n, i genap   3, i = n Ketika i ganjil    2, 1 ≤ j ≤ m − 2, j ganjil c(xi,j ) = 3, 1 ≤ j ≤ m − 1, j genap   4, j = m, m ganjil

Ketika i genap    1, 1 ≤ j ≤ m, j ganjil c(xi,j ) = 3, 1 ≤ j ≤ m, j genap   4, j = m, m ganjil


6

Ketika i = n    1, 1 ≤ j ≤ m − 2, j ganjil c(xi,j ) = 2, 1 ≤ j ≤ m − 1, j genap   4, j = m, m ganjil

Sehingga terbukti bahwa graf G = (Cn ⊙ Cm ) mempunyai bilangan kromatik pewarnaan titik dinamis untuk untuk n genap maka χ(G) = χd (G)= 3 2 3 ketika m genap, χ(G) = χd (G)= 4 ketika m = ( 4k −21k3 +41k−9 ), kǫN , dan χ(G) = χd (G) = χ3 (G)= 4 ketika m = 6k − 3, kǫN saat m ganjil. Untuk n ganjil, maka χ(G) = χd (G)= 3 ketika m genap, χ(G) = χd (G)= 4 ketika m = 3 2 ( 4k −21k3 +41k−9 ), kǫN , dan χ(G) = χd (G) = χ3 (G)= 4 ketika m = 6k − 3, kǫN saat m ganjil. 2 Open Problem 3 Misalkan G adalah hasil crown product dari Cn dan Cm . Untuk n ≥ 3 dan m ≥ 3, tentukan bilangan kromatik r-dynamic dari graf G ketika r ≥ 3. 3 Teorema 9 Jika G= (Cn ⊗ Cm ) untuk n ≥ 3 dan m ≥ 3, pewarnaan titik dinamis dari graf G adalah Untuk n genap χ(G) = 2, untuk m ganjil Untuk n ganjil χ(G) = 3, untuk n dan m =

4k 3 −21k 2 +41k−9 , kǫN 3

χ(G) = χd (G) = 3, untuk m = 6k − 3, kǫN Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf (Cn ⊗ Cm ) bahwa |V | = p = nm dan |E| = q = 8nm − 16n − 12m + 24 maka batas atas dari bilangan kromatik adalah χ(Cn ⊗ Cm ) ≤ ( 17nm−32n−24m+48 ). Fungsi pewarnaan titik pada graf G = (Cn ⊗ Cm ) nm adalah Untuk n atau m genap ( 1, 1 ≤ i ≤ n, i ganjil; 1 ≤ j ≤ m c(xi,j ) = 2, 1 ≤ i ≤ n, i genap; 1 ≤ j ≤ m Untuk n atau m ganjil    1, 1 ≤ i ≤ n; 1 ≤ j ≤ m, j ganjil c(xi,j ) = 2, 1 ≤ i ≤ n; 1 ≤ j ≤ m − 1, j genap   3, 1 ≤ i ≤ n; j = m


7

Sehingga terbukti bahwa graf G = (Cn ⊗ Cm ) mempunyai bilangan kromatik pewarnaan dinamis untuk n genap χ(G)= 2 ketika m genap atau ganjil 3 2 dan untuk n ganjil χ(G)=3 ketika n dan m adalah 4k −21k3 +41k−9 , kǫN , dan χ(G) = χd (G)= 3 ketika m = 6k − 3, kǫN saat m ganjil. 2 Open Problem 4 Misalkan G adalah hasil operasi tensor product dari Cn pada Cm . Untuk n ≥ 3 dan m ≥ 3, tentukan bilangan kromatik r-dynamic dari G ketika r ≥ 4. 3 Teorema 10 Jika G adalah cartesian product dari graf lingkaran (Cn ) dan lingkaran (Cm ). Untuk n ≥ 3 dan m ≥ 3, pewarnaan dinamis G = (Cn Cm ) adalah untuk n genap χ(G) = 2, untuk m genap untuk n ganjil χ(G) = 3, untuk n =

4k 3 −21k 2 +41k−9 , kǫN, 3

m genap atau ganjil

χ(G) = χd (G) = 3, untuk n = 6k − 3, kǫN, m genap atau ganjil Bukti. BBerdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf (Cn Cm ) bahwa |V | = p = nm dan |E| = q = 2nm maka batas atas dari bilangan kromatik adalah χ(Cn Cm ) ≤ ( 5nm nm ). Fungsi pewarnaan titik pada graf G = (Cn Cm ) adalah Untuk n genap dan m genap ( 1, 1 ≤ i ≤ n, i ganjil; 1 ≤ j ≤ m, j ganjil c(xi,j ) = 2, 1 ≤ i ≤ n − 1, i genap; 1 ≤ j ≤ m − 1, j genap Untuk n ganjil m genap ketika i ganjil    1, 1 ≤ i ≤ n − 2; 1 ≤ j ≤ m − 2, j ganjil c(xi,j ) = 2, 1 ≤ i ≤ n − 2; 1 ≤ j ≤ m − 1, j genap   3, 1 ≤ i ≤ n − 2; j = m ketika i genap

   1, 1 ≤ i ≤ n − 1; j = m c(xi,j ) = 2, 1 ≤ i ≤ n − 1; 1 ≤ j ≤ m, j ganjil   3, 1 ≤ i ≤ n − 1; 1 ≤ j ≤ m, j genap


8

ketika i = n    1, 1 ≤ i ≤ n; 1 ≤ j ≤ m, j genap c(xi,j ) = 2, 1 ≤ i ≤ n; 1 ≤ j ≤ m, j = m   3, i = n; 1 ≤ j ≤ m, j ganjil

Sehingga terbukti bahwa graf G = (Cn Cm ) mempunyai bilangan kromatik pewarnaan titik dinamis untuk n genap, maka χ(G)= 2 ketika m genap. 3 2 Untuk n ganjil= 4k −21k3 +41k−9 , kǫN , bilangan kromatik pewarnaan titik dinamis χ(G)= 3 ketika m genap atau ganjil, dan χ(G) = χd (G)= 3 untuk n = = 6k − 3, kǫN ketika n ganjil saat m genap atau ganjil. 2 Open Problem 5 Misalkan G adalah cartesian produc dari hasil cartesian Cn and Cm . Untuk n ≥ 3 dan m ≥ 3, tentukan bilangan kromatik r-dynamic dari G untuk r ≥ 2. 3 Teorema 11 Jika G= (Sn 2Pm ). Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik pewarnaan dinamis G = (Sn 2Pm ) adalah χ(G) =

2, untuk n m ganjil genap

Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf (Sn 2Pm ) bahwa |V | = p = nm + m dan |E| = q = nm + 5m − 5 maka batas atas dari bilangan kromatik adalah χ(Sn 2Pm ) ≤ 3nm+3m ( nm+11m−10 ). Fungsi pewarnaan titik pada graf G = (Sn 2Pm ) adalah c(Axj ) =

(

1, 1 ≤ j ≤ m, j ganjil 2, 1 ≤ j ≤ m − 1, j genap

Untuk m genap atau ganjil ( 1, 1 ≤ i ≤ n, 1 ≤ j ≤ m − 1, j genap c(xi,j ) = 2, 1 ≤ i ≤ n, 1 ≤ j ≤ m, j ganjil Sehingga terbukti bahwa graf G = (Sn 2Pm ) mempunyai bilangan kromatik χ(G)= 2 untuk m genap dan m ganjil. Pewarnaan dinamis graf G adalah χ(G)=χd (G) = 2 untuk m genap dan m ganjil. 2 Open Problem 6 Misalkan G adalah cartesian produc dari hasil cartesian Sn dan Pm . Untuk n ≥ 3 dan m ≥ 2, tentukan bilangan kromatik r-dynamic dari G untuk r ≥ 2.

9


3 Teorema 12 Jika G= (Cn [Cm ]). Untuk n ≥ 3 dan m ≥ 3, bilangan kromatik dan pewarnaan titik dinamis G adalah untuk n genap ( 4, untuk m genap χ(G) = χd (G) = χ3 (G) = 3 2 6, untuk m = 4k −21k3 +41k−9 , kǫN χ(G) = χd (G) = χ3 (G) = χ4 (G) = χ5 (G) =

6, untuk m = 6k − 3, kǫN

untuk n ganjil χ(G) = χd (G) = χ3 (G) = χ4 (G) = χ5 (G) =

9, untuk m =

χ(G) = χd (G) = χ3 (G) = χ4 (G) = χ5 (G) = χr (G) =

4k 3 −21k 2 +41k−9 , kǫN 3

9, untuk m = 6k − 3, kǫN

Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf (Cn [Cm ]) bahwa |V | = p = nm dan |E| = q = 10nm− 16n − 12m + 24 maka batas atas dari bilangan kromatik adalah χ(Cn [Cm ]) ≤ ( 21nm−32n−24m+24 ). Fungsi pewarnaan titik pada graf G = (Cn [Cm ]) adalah nm Untuk n genap   1, 1 ≤ i ≤ n − 1, i ganjil; 1 ≤ j ≤ m − 2, j ganjil      2, 1 ≤ i ≤ n, i genap; 1 ≤ j ≤ m − 2 j ganjil     3, 1 ≤ i ≤ n − 1, i ganjil; 1 ≤ j ≤ m − 1, j genap f (xi,j ) =  4, 1 ≤ i ≤ n, i genap; 1 ≤ j ≤ m − 1, j genap      5, 3 ≤ i ≤ n − 1, i ganjil; 3 ≤ j ≤ m, j = m     6, 3 ≤ i ≤ n, i genap; 3 ≤ j ≤ m, j = m Untuk n ganjil                   f (xi,j ) =                 

1, 2, 3, 4, 5, 6, 7, 8, 9,

1 ≤ i ≤ n − 2, i ganjil; 1 ≤ j ≤ m − 2, j ganjil 1 ≤ i ≤ n − 1, i ganjil; 1 ≤ j ≤ m − 1, j genap 1 ≤ i ≤ n, i ganjil; 3 ≤ j ≤ m, j = m 1 ≤ i ≤ n − 1, i genap; 1 ≤ j ≤ m − 2, j ganjil 1 ≤ i ≤ n − 1, i genap; 1 ≤ j ≤ m − 1, j genap 1 ≤ i ≤ n − 1, i genap; 1 ≤ j ≤ m, j = m 1 ≤ i ≤ n, i = n; 1 ≤ j ≤ m − 2, j ganjil 1 ≤ i ≤ n, i = n; 1 ≤ j ≤ m − 1, j genap 1 ≤ i ≤ n, i = n; 1 ≤ j ≤ m, j = m

Sehingga terbukti bahwa graf G = (Cn [Cm ]) mempunyai bilangan kromatik dan pewarnaan titik dinamis untuk n genap χ(G) = χd (G) = χ3 (G)= 3 2 4 ketika m genap, 6 ketika m = 4k −21k3 +41k−9 , kǫN , dan χ(G) = χd (G) =


10

χ3 (G) = χ4 (G) = χ5 (G)= 6, ketika m = 6k − 3, kǫN saat m ganjil. Untuk n ganjil, maka χ(G) = χd (G) = χ3 (G) = χ4 (G) = χ5 (G)= 9 ketika m = 4k 3 −21k 2 +41k−9 , kǫN , dan χ(G) = χd (G) = χ3 (G) = χ4 (G) = χ5 (G) = χr (G)=9 3 ketika m dan n= 6k − 3, kǫN saat m dan n ganjil. 2 Open Problem 7 Misalkan G adalah cartesian produc dari hasil cartesian dari Cn and Cm . Untuk n ≥ 3 and m ≥ 2, tentukan bilangan kromatik rdynamic dari G untuk r ≥ 4. 3 Teorema 13 Jika G Amal(Cn , v = 1, m). Untuk n ≥ 3, bilangan kromatik dan pewarnaan titik dinamis G adalah ( 2, untuk n genap χ(G) 3 2 3, untuk m = 4k −21k3 +41k−9 , kǫN χ(G) = χd (G) = 3, untuk n = 6k − 3, kǫN Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf Amal(Cn , v = 1, m) bahwa |V | = p = nm−m+1 dan |E| = q = nm maka batas atas dari bilangan kromatik adalah χAmal(Cn , v = 1, m) ≤ ( 3nm−m+1 nm−m+1 ). Fungsi pewarnaan titik pada graf G = Amal(Cn , v = 1, m) adalah f (A) = 1 Untuk n genap f (xi,j ) =

(

1, 2 ≤ i ≤ n − 2, i genap; 1 ≤ j ≤ m 2, 1 ≤ i ≤ n − 1, i ganjil; 1 ≤ j ≤ m

Untuk n ganjil    1, 3 ≤ i ≤ n − 3, i ganjil; 1 ≤ j ≤ m f (xij ) = 2, 1 ≤ i ≤ n − 2, i ganjil; 1 ≤ j ≤ m   3, 2 ≤ i ≤ n, i genap; 1 ≤ j ≤ m

Sehingga terbukti bahwa graf G = (Amal(Cn , v = 1, m)) mempunyai bilangan kromatik dan pewarnaan titik dinamis yaitu χ(G)= 2 ketika n genap, dan 3 2 3 ketika m = 4k −21k3 +41k−9 , kǫN serta χ(G) = χd (G)= 3 ketika n = 6k−3, kǫN . 2 Open Problem 8 Misalkan G adalah amalgamation dari graf Cn , untuk n ≥ 3, tentukan bilangan kromatik r-dynamic dari G untuk r ≥ 3.


11

3 Teorema 14 Jika G = (Amal(Cn + Pm , v = 1, r)). Untuk n ≥ 3 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G adalah ( 4, untuk n genap χ(G) = χd (G) = χ3 (G) 3 2 5, untuk n = 4k −21k3 +41k−9 , kǫN χ(G) = χd (G) = χ3 (G) = χ4 (G) = 5, untuk n = 6k − 3, kǫN Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf Amal(Cn + Pm , v = 1, r) bahwa |V | = p = nr + mr − r + 1 dan |E| = q = nmr + nr + mr + −r maka batas atas dari bilangan kromatik adalah χ(Amal(Cn + Pm , v = 1, r)) ≤ ( 2nmr+3nr+3mr−3r+1 ). Fungsi pewarnaan nr+mr−r+1 titik pada graf G = Amal(Cn + Pm , v = 1, r) adalah c(y1 ) = 1

c(yj k ) =

(

1, 3 ≤ j ≤ m, j ganjil, 1 ≤ k ≤ r 2, 2 ≤ j ≤ m − 1, j genap, 1 ≤ k ≤ r

Untuk n genap atau ganjil    3, 1 ≤ i ≤ n − 1, i ganjil, 1 ≤ k ≤ r c(yj k ) = 4, 1 ≤ i ≤ n, i genap, 1 ≤ k ≤ r   5, i = n, 1 ≤ k ≤ r

Sehingga terbukti bahwa graf G = (Amal(Cn + Pm , v = 1, r)) mempunyai bilangan kromatik dan pewarnaan titik dinamis χ(G) = χd (G) = χ3 (G)= 4 3 2 ketika n genap, dan 5 ketika n = 4k −21k3 +41k−9 , kǫN serta χ(G) = χd (G) = χ3 (G) = χ4 (G)= 5 ketika n = 6k − 3, kǫN saat. 2 Open Problem 9 Misalkan G adalah amalgamasi dari hasil joint Cn and Pm . Untuk n ≥ 3 and m ≥ 2, tentukan bilangan kromatik r-dynamic dari G untuk r ≥ 5. 3 Teorema 15 Jika G = (Shack(Cn + Pm , r)). Untuk n ≥ 4 dan m ≥ 2, bilangan kromatik dan pewarnaan titik dinamis G adalah ( 4, untuk n genap χ(G) = χd (G) = χ3 (G) 3 2 5, untuk n = 4k −21k3 +41k−9 , kǫN

χ(G) = χd (G) = χ3 (G) = χ4 (G) = 5, untuk n = 6k − 3, kǫN

12


Bukti. Berdasarkan Teorema 3 yang dinyatakan bahwa (χ − 1)p ≤ 2q. Sesuai dengan observasi pada graf Shack(Cn + Pm , r) bahwa |V | = p = nr + mr − r + 1 dan |E| = q = nmr + 2nr + mr − 5r maka batas atas dari bilangan kromatik adalah χ(Shack(Cn + Pm , r)) ≤ ( 2nmr+5nr+3mr−11r+1 ). nr+mr−r+1 Fungsi pewarnaan titik pada graf G = (Shack(Cn + Pm , r)) adalah ( 3, 1 ≤ j ≤ m, j ganjil; 1 ≤ k ≤ r k c(yi ) = 4, 1 ≤ j ≤ m − 1, j genap; 1 ≤ k ≤ r Untuk n genap c(p) = 2   1, 1 ≤ i ≤ n − 1, i ganjil; 1 ≤ k ≤ r, k ganjil     1, 1 ≤ i ≤ n − 1, i genap; 1 ≤ k ≤ r, k genap c(yik ) =  2, 1 ≤ i ≤ n, i genap; 1 ≤ k ≤ r, k ganjil     2, 1 ≤ i ≤ n − 1, i ganjil; 1 ≤ k ≤ r, k genap

Untuk n ganjil

c(p) = 3   1, 1 ≤ i ≤ n − 2, i ganjil; 1 ≤ k ≤ r,       1, 1 ≤ i ≤ n − 2, i ganjil; 1 ≤ k ≤ r, k c(yi ) = 2, 1 ≤ i ≤ n − 1, i genap; 1 ≤ k ≤ r,    2, 1 ≤ i ≤ n − 1, i genap; 1 ≤ k ≤ r,     3, i = n; 1 ≤ k ≤ r, k genap

k ganjil k genap k ganjil k genap

Sehingga terbukti bahwa graf G = (Shack(Cn + Pm , v = r)) mempunyai bilangan kromatik dan pewarnaan titik dinamis χ(G)=χd (G)=χ3 (G)= 4 untuk 3 2 n genap dan 5 untuk n = 4k −21k3 +41k−9 , kǫN serta χ(G) = χd (G) = χ3 (G) = χ4 (G)= 5 ketika n= 6k − 3, kǫN saat n ganjil. 2 Open Problem 10 Misalkan G adalah shackle dari hasil joint Cn and Pm . Untuk n ≥ 3 and m ≥ 2, tentukan bilangan kromatik r-dynamic dari G untuk r ≥ 5.

Kesimpulan Penelitian ini telah menemukan pewarnaan r-dynamic dari beberapa operasi graf. Hasil penelitian menunjukkan untuk masing-masing operasi graf, tidak diperoleh semua nilai dari r. Oleh karena itu, kami masih membuka open problem untuk peneliti lain. Berdasarkan hasil penelitian di atas, maka dapat disimpulkan bahwa pewarnaan r-dynamic dari beberapa operasi graf ditemukan 10 teorema dan 3 akibat dari teorema sebelumnya.


13

References [1] J.L. Gross, J. Yellen and P. Zhang, Handbook of Graph Theory, Second Edition, CRC Press, Taylor and Francis Group, 2014 [2] S.J. Kim and W.J. Park, List dynamic coloring of sparse graphs, Combinatorial optimization and applications. Lect. Notes Comput. Sci. 6831 (Springer, 2011), 156 162. [3] S.J. Kim, S. J. Lee, and W.J. Park, Dynamic coloring and list dynamic coloring of planar graphs. Discrete Applied Math. 161 (2013), 22072212. [4] S. Akbari, M. Ghanbari, S. Jahanbekam, On the dynamic chromatic number of graphs, Combinatorics and graphs. Contemp. Math. 531 (Amer. Math. Soc. 2010), 118. [5] B. Montgomery, Dynamic Coloring of Graphs. Ph.D Dissertation, West Virginia University, 2001. [6] H.J. Lai, B. Montgomery, and H. Poon, Upper bounds of dynamic chromatic number. Ars Combin. 68 (2003), 193201. [7] S Jahanbekam, J Kim, O Suil, D.B. West, On r-dynamic Coloring of Graphs, 2014, Discrete Applied Mathematics. 157 (2009) 3005-3007. [8] L. Esperet, Dynamic list coloring of bipartite graphs. Discrete Applied Mathematics. 158 (2010) 1963-1965. [9] A. Meyshahi, On the dynamic coloring of graphs. Discrete Applied Mathematics. 159 (2011) 152-156. [10] N. Mohanapriya, S. V. Kumar, J. Vernold, M. Venkatachalam, On dynamic cromathic number of 4-regulergraphs with girth 3 dan 4. (submitted) [11] Osserman, On upper bound of cromathic number. (submitted)

Abstract

Recommend Documents