The r-Dynamic Chromatic Number of Special Graph Operations Nindya Laksmita2 , Dafik1,2 , A.I. Kristiana1,2 1 CGANT-
University of Jember of Mathematics Education - University of Jember
[email protected];
[email protected]
2 Department
2010 Mathematics Subject Classification: 05C69 Abstract Let G be a simple, connected and undirected graph. Let r, k be natural number. By a proper k-coloring of a graph G, we mean a map c : V (G) → S, where |S| = k, such that any two adjacent vertices receive different colors. 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. In this paper, we will show some exact values of χr (G) when G is an operation of special graphs.
Keywords: r-dynamic coloring, chromatic number, shackle, graph operations.
Pendahuluan Salah satu teori yang dikembangkan dalam teori graf adalah pewarnaan (colouring). Terdapat tiga macam pewarnaan dalam teori graf, yaitu pewarnaan titik (vertex colouring), pewarnaan sisi face colouring, dan pewarnaan wilayah region colouring. Pewarnaan titik (vertex colouring) adalah pemberian warna pada titik-titik graf dimana dua titik yang bertetangga diberi warna yang berbeda. Selain itu, jumlah warna yang digunakan pada pewarnaan graf adalah jumah warna paling sedikit digunakan (minimum). Pada graf G, jumlah warna minimum yang digunakan untuk mewarnai graf G disebut sebagai bilangan kromatik, yang dinotasikan dengan X (G). Pada perkembangannya, penelitian tentang pewarnaan titik pada graf tidak hanya sebatas pada pewarnaan titik biasa, tapi juga terdapat pewarnaan titik lainnya yang disebut dengan pewarnaan dinamis yang akhirnya juga berkembang menjadi pewarnaan r-dinamis. Penelitian-penelitian mengenai pewarnaan dinamis cukup banyak dilakukan oleh peneliti, beberapa diantaranya adalah Lai dan Montgomery (2002) dalam artikelnya yang berjudul ”Dynamic Coloring of Graphs”, Kim (2012) dalam penelitiannya yang berjudul ”Dynamic Coloring and List Dynamic Coloring of Planar Graphs”. Kang,
The r-Dynamic Chromatic Number of Spesial Graph Operations . . .
2
dkk. (2014) melakukan penelitian berjudul ”On r-dynamic Coloring of Grids” dan Jahanbekam, dkk. (2014) juga melakukan penelitian berjudul ”On r−-dynamic Coloring of Graphs”. Mereka mengkaji pewarnaan r-dinamis pada graf yang sebelumnya telah diperkenalkan oleh Montgomery. Hasil penelitian terkait ini terdapat pada [1, 3]. Pada penelitian ini akan dikaji mengenai pewarnaan r-dinamis pada graf-graf hasil operasi dan graf sikel. Penelitian ini merupakan pengembangan dari penelitianpenelitian sebelumnya yang mengkaji tentang nilai kromatik r-dinamis pada operasi graf dan shackle.
Teorema yang Digunakan Theorem 1 (Vizing Theorem). Jika G adalah graph sederhana, maka bilangan kromatik pewarnaan titiknya χ(G) berada pada interval ini χ(G) ≤ ∆(G) + 1. Theorem 2 [9] If diam(G) = 2, then χ2 (G) ≤ χ(G) + 2, with equality holds only when G is a complete bipartite graph or C5 . Theorem 3 [9] If G is a k-chromatic graph with diameter at most 3, then χ2 (G) ≤ 3k, and this bound is sharp when k ≥ 2. In term of the maximum degree of graph, the r-dynamic of graph satisfies as follows Observation 1 [9] χr (G) ≥ min{∆(G), r} + 1, and this is sharp. If ∆(G) ≤ r then χr (G) = min{∆(G), r}. Theorem 4 [9] χr (G) ≤ r∆(G) + 1, with equality for r ≥ 2 if and only if G is r-regular with diameter 2 and girth 5. Let G2 denote the graph obtained from G by adding edges joining nonadjacent vertices that have a common neighbor, Jahanbekam et. al [9] proved the following. Observation 2 [9] χ(G) ≤ χd (G) ≤ χ3 (G) ≤ · · · ≤ χ∆(G) (G) = χ(G2 ). The last, for graph operations of cartesian product, we have the following Theorem 5 [9] If δ(G) ≥ r then χr (G2H) = max{χ(G), χ(H)}.
Hasil Penelitian Berikut ini akan disajikan beberapa temuan baru terkait nilai kromatik r-dinamis J pada operasi graf diantaranya adalah Shackle(F4 , e, n) , dan G = Pn Pm . Hasil penelitian dalam artikel ini berupa teorema, yang dalam hal ini terdapat dua teorema kemudian disertai bukti-bukitinya. Teorema pertama terkait dengan Shackle(F4 , e, n).
The r-Dynamic Chromatic Number of Spesial Graph Operations . . .
3
Theorem 1 Jika G = Shackle(F4 , e, n) untuk n ≥ 2 , nilai kromatik r − dinamis dari graf G adalah χ(G) = χd (G) = 3, χ3 (G) = 4 , χ4 (G) = 5 , χr (G) = 6 Bukti. Graf Shackle(F4 , e, n) memiliki himpunan titik V = {xi , yj ; 1 ≤ i ≤ n + 1}∪ {zi ; 1 ≤ i ≤ n} dan himpunan sisi E = {xi yi ; 1 ≤ i ≤ n + 1} ∪ {xi zi ; 1 ≤ i ≤ n} ∪ {yi zi ; 1 ≤ i ≤ n+}∪{yi yi+1 ; 1 ≤ i ≤ n}∪{xi+1 zi ; 1 ≤ i ≤ n}∪{yi+1 zi ; 1 ≤ i ≤ n}. Kemudian order dan sizenya adalah masing-masing p = |V | = 3n + 2 dan q = |E| = 6n + 1, derajad tertingginya ∆(G) = 5. Sesuai dengan batas atas bilangan kromatik r − dinamis untuk graf Shackle(F4 , e, n) adalah χr (G) ≥ min{∆(G), r} + 1 = {5, r} + 1, sehingga untuk graf Shackle(F4 , e, n), dengan ∆(G) = 5 berlaku χ(G) ≤ ∆(G) + 1 = 6. Pertama akan dibuktikan χ(G) = χd (G) = 3. Fungsi titik Shackle(F4 , e, n) untuk n ≥ 2 ½ 1; i = ganjil; 1 ≤ i ≤ n f (xi ) = 2; i = genap; 2 ≤ i ≤ n − 1 ½ f (yi ) =
2; i = ganjil; 1 ≤ i ≤ n − 1 1; i = genap; 2 ≤ i ≤ n
f (zi ) =
©
3; ; 1 ≤ i ≤ n
Sehingga terbukti bahwa graf G = Shackle(F4 , e, n) untuk n ≥ 2 mempunyai bilangan kromatik χ(G) = 3 dan mempunyai pewarnaan dinamis χ(G) = χd (G) = 3. Kedua akan dibuktikan χ3 (G) = 4. Fungsi titik Shackle(F4 , e, n) untuk n ≥ 2 © f (xi ) = 1; ; 1 ≤ i ≤ n + 1 2; f (yi ) = 3; 4; 2; f (zi ) = 3; 4;
i ≡ 5 (mod 3), 1 ≤ i ≤ n i ≡ 3 (mod 3), 1 ≤ i ≤ n i ≡ 4 (mod 3), 1 ≤ i ≤ n i ≡ 4 (mod 3), 1 ≤ i ≤ n i ≡ 5 (mod 3), 1 ≤ i ≤ n i ≡ 3 (mod 3), 1 ≤ i ≤ n
Sehingga terbukti bahwa graf G = Shackle(F4 , e, n) untuk n ≥ 2 mempunyai bilangan kromatik χ(G) = 4 dan mempunyai pewarnaan dinamis χ3 (G) = 4. Ketiga akan dibuktikan χ4 (G) = 5. Fungsi titik Shackle(F4 , e, n) untuk n ≥ 2 1; i ≡ 5 (mod 3), 1 ≤ i ≤ n f (xi ) = 3; i ≡ 3 (mod 3), 1 ≤ i ≤ n 5; i ≡ 4 (mod 3), 1 ≤ i ≤ n ½ f (yi ) =
2, i = ganjil; 1 ≤ i ≤ n − 1 4, i = genap; 2 ≤ i ≤ n
The r-Dynamic Chromatic Number of Spesial Graph Operations . . .
4
1; i ≡ 4 (mod 3), 1 ≤ i ≤ n f (zi ) = 3; i ≡ 5 (mod 3), 1 ≤ i ≤ n 5; i ≡ 3 (mod 3), 1 ≤ i ≤ n Sehingga terbukti bahwa graf G = Shackle(F4 , e, n) untuk n ≥ 2 mempunyai bilangan kromatik χ(G) = 5 dan mempunyai pewarnaan dinamis χ4 (G) = 5. Keempat akan dibuktikan χr (G) = 6. Fungsi titik Shackle(F4 , e, n) untuk n ≥ 2 1; i ≡ 5 (mod 3), 1 ≤ i ≤ n f (xi ) = 2; i ≡ 3 (mod 3), 1 ≤ i ≤ n 5; i ≡ 4 (mod 3), 1 ≤ i ≤ n 1; f (yi ) = 2; 4; ½ 3; f (zi ) = 6;
i ≡ 3 (mod 3), 1 ≤ i ≤ n i ≡ 5 (mod 3), 1 ≤ i ≤ n i ≡ 4 (mod 3), 1 ≤ i ≤ n i = ganjil; 1 ≤ i ≤ n − 1 i = genap; 1 ≤ i ≤ n
Sehingga terbukti bahwa graf G = Shackle(F4 , e, n) untuk n ≥ 2 mempunyai bilangan kromatik χ(G) = 6 dan mempunyai pewarnaan dinamis χn (G) = 6. J Theorem 2 Jika G = Pn Pm Untuk m ≥ 2 dan n ≥ 2, nilai kromatik (rdinamis)dari graf G adalah χ(G) = χd (G) = 3, χ3 (G) = 4 , χ4 (G) = 5 , χr (G) = 2m + 1 J Bukti. Graf G = Pn Cm memiliki himpunan titik V = {xi , xij ; 1 ≤ i ≤ n; 1 ≤ j ≤ m} dan himpunan sisi E = {xi xi+1 ; 1 ≤ i ≤ n − 1}∪{xi xij ; 1 ≤ i ≤ n; 1 ≤ j ≤ m} ∪{xij xij+1 ; 1 ≤ i ≤ n; 1 ≤ j ≤ m − 1, }. Kemudian order dan sizenya adalah masingmasing p = |V | = n(1 + m) dan q = |E| = 2mn − 1, derajad tertingginya ∆(G) = J m+2. Sesuai dengan batas atas bilangan kromatik r −dinamis untuk graf Pn Cm J adalah χr (G) ≥ min{∆(G), r} + 1 = {m + 2, r} + 1, sehingga untuk graf Pn Pm , dengan ∆(G) = m + 2 berlaku χ(G) ≤ ∆(G) + 1 = m + 3. Pertama akan dibuktikan χ(G) = χd (G) = 3. Fungsi titik Pn ¯ Pm untuk n ≥ 2 dan m = 2 ½ 1, i = ganjil; 1 ≤ i ≤ n − 1 f (xi ) = 2, i = genap; 2 ≤ i ≤ n 1, 2, f (xi,j ) = 3, 3,
i i i i
= = = =
genap; ganjil; ganjil; genap;
2 ≤ i ≤ n, j = ganjil; 1 ≤ j ≤ m − 2 1 ≤ i ≤ n − 1, j = ganjil; 1 ≤ j ≤ m − 2 1 ≤ i ≤ n − 1, j = genap; 2 ≤ j ≤ m − 1 2 ≤ i ≤ n, j = genap; 2 ≤ j ≤ m − 1
Sehingga terbukti bahwa graf G = Pn ¯ Pm untuk n ≥ 2 dan m = 2 mempunyai bilangan kromatik χ(G) = 3 dan mempunyai pewarnaan dinamis χ(G) = χd (G) = 3.
The r-Dynamic Chromatic Number of Spesial Graph Operations . . .
5
Kedua akan dibuktikan χ3 (G) = 4. Fungsi titik Pn ¯ Pm untuk n ≥ 2 dan m = 2 ½ 1, i = ganjil; 1 ≤ i ≤ n − 1 f (xi ) = 2, i = genap; 2 ≤ i ≤ n ½ f (xi,j ) =
3, 4,
2 ≤ i ≤ n; 1 ≤ j ≤ m − 1 1 ≤ i ≤ n; 1 ≤ j ≤ m
Sehingga terbukti bahwa graf G = Pn ¯ Pm untuk n ≥ 2 dan m = 2 mempunyai bilangan kromatik χ(G) = 4 dan mempunyai pewarnaan dinamis χ3 (G) = 4. Ketiga akan dibuktikan χr (G) = 4. Fungsi titik Pn ¯ Pm untuk n ≥ 2 dan m = 2 1; i ≡ 5 (mod 3), 1 ≤ i ≤ n f (xi ) = 2; i ≡ 4 (mod 3), 1 ≤ i ≤ n 3; i ≡ 3 (mod 3), 1 ≤ i ≤ n ½ f (xi,j ) =
4, 5,
2 ≤ i ≤ n; 1 ≤ j ≤ m − 1 1 ≤ i ≤ n; 1 ≤ j ≤ m
Sehingga terbukti bahwa graf G = Pn ¯ Pm untuk n ≥ 2 dan m = 2 mempunyai bilangan kromatik χ(G) = 5 dan mempunyai pewarnaan dinamis χr (G) = 5. Jika pada graf G = Pn ¯ Pm untuk n ≥ 2 dan m ≥ 2 maka χr (G) = 2m + 1
Kesimpulan Dari penelitian diatas dapat disimpulkan bahwa: χr (Shackle(F4 , e, n)) = 6 χr (Pn ¯ Pm ) = 2m + 1
References [1] Desy Tri Puspasari, Dafik Dafik, Slamin Slamin, Pewarnaan Titik pada Graf Khusus: Operasi dan Aplikasinya, Prosiding Seminar Matematika dan Pendidikan Matematik, Vol. 2, Issue 1, (2014), 50-58 [2] J.L. Gross, J. Yellen and P. Zhang, Handbook of Graph Theory, Second Edition, CRC Press, Taylor and Francis Group, 2014 [3] Harsya Alfian Yulia, Dafik Dafik, Ika Hesti Agustin, Bilangan Kromatik pada Pengoperasian Graf Lintasan dengan Graf Lingkaran, Proceeding of International Workshop on Mathematics UAD, (2014), 1-18 [4] 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.
The r-Dynamic Chromatic Number of Spesial Graph Operations . . .
6
[5] 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. [6] S. Akbari, M. Ghanbari, S. Jahanbekam, On the dynamic chromatic number of graphs, Combinatorics and graphs. Contemp. Math. 531 (Amer. Math. Soc. 2010), 118. [7] B. Montgomery, Dynamic Coloring of Graphs. Ph.D Dissertation, West Virginia University, 2001. [8] H.J. Lai, B. Montgomery, and H. Poon, Upper bounds of dynamic chromatic number. Ars Combin. 68 (2003), 193201. [9] S Jahanbekam, J Kim, O Suil, D.B. West, On r-dynamic Coloring of Graphs, 2014, In Press [10] R.L. Brooks, On colouring the nodes of a network. Proc. Cambridge Philos. Soc. 37 (1941), 194197.