On r-dynamic coloring of some graph operations

Abstract

Let G be a simple, connected and undirected graph. Given r; k as any natural numbers. By an r-dynamic k-coloring of graph G, we mean a proper k-coloring c(v) of G such that jc(N(v))j minfr; d(v)g for each vertex v in V (G), where N(v) is the neighborhood of v. The r-dynamic chromatic number, written as (G), is the minimum k such that G has an r-dynamic k-coloring. We note that the 1-dynamic chromatic number of graph is equal to its chromatic number, denoted by (G), and the 2-dynamic chromatic number of graph has been studied under the name a dynamic chromatic number, denoted by r (G). By simple observation, we can show that

r (G) r+1 (G), however r+1 (G) r d (G) can be arbitrarily large, for example (Petersen) = 2; d (Petersen) = 3, but 3 (Petersen) = 10. Thus, finding an exact values of (G) is not trivially easy. This paper will describe some exact values of (G) when G is an operation of special graphs.