%\documentclass[12pt,twoside,a4,bezier,color,epsfig,amsfonts,graphicx,amsmath,amssymb,alltt,epsf,psfig]{article}
\documentstyle[11pt,a4,bezier,color,epsfig,amsfonts,graphicx,amsmath,amssymb,alltt,epsf,psfig]{article}

\renewcommand{\baselinestretch}{1}
\def\refname {\bf References}
\newtheorem{Theor} {Theorem}
\newtheorem{lemma} {Lemma}
\newtheorem{definition} {Definition}[section]
\newtheorem{example} {Example}[section]
\newtheorem{claim} {Claim}[section]
\newtheorem{corollary} {Corollary}
\newtheorem{openproblem} {Open Problem}
\newtheorem{conjecture} {Conjecture}
\newtheorem{proposition} {Proposition}
\newtheorem{observation} {Observation}
\def\abstractname {\bf Abstract}
\def\bibname {\bf References}
\def\figurename {Figure}
\newcommand{\ebox}{\hfill $\Box$\\\vspace{-2mm}}

\setcounter{page}{1}

\setlength{\textheight}{21.6cm}
\setlength{\textwidth}{14cm}
\setlength{\oddsidemargin}{1cm}
\setlength{\evensidemargin}{1cm}
\pagestyle{myheadings}

\thispagestyle{empty}

\markboth{\small{I.H. Agustin, Dafik, A.Y. Harsya}}{\small{On the
Domination Number of Some Graph Operations \dots}}

\date{}

\renewcommand{\baselinestretch}{1.05}
\begin{document}

\centerline {\Large{\bf On $r$-Dynamic Coloring of Some Graph
Operations}}

\begin{center}
I.H. Agustin$^{1,2}$, Dafik$^{1,3}$, A.Y. Harsya$^{2}$\\
\centerline{}
$^{1}$CGANT- University of Jember\\
$^{2}$Department of Mathematics - University of Jember\\
$^{3}$Department of Mathematics Education - University of Jember\\
Hestyarin@gmail.com; d.dafik@unej.ac.id\\
\end{center}

\centerline{} \centerline{{\it 2010 Mathematics Subject
Classification: 05C69}}

\begin{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) \rightarrow 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))| \geq 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 \in S\}$ for a vertex subset $S$ . The $r$-dynamic chromatic
number, written as $\chi_r(G)$, is the minimum $k$ such that $G$ has
an $r$-dynamic $k$-coloring. Note that the $1$-dynamic chromatic
number of graph is equal to its chromatic number, denoted by
$\chi(G)$, and the $2$-dynamic chromatic number of graph has been
studied under the name a dynamic chromatic number, denoted by
$\chi_d(G)$. By simple observation it is easy to see that
$\chi_r(G)\le \chi_{r+1}(G)$, however $\chi_{r+1}(G)-\chi_r(G)$ can
be arbitrarily large, for example
$\chi(Petersen)=2,\chi_d(Petersen)=3$, but $\chi_3(Petersen)=10$.
Thus, finding an exact values of $\chi_r(G)$ is significantly
useful. In this paper, we will show some exact values of $\chi_r(G)$
when $G$ is an operation of special graphs.
\end{abstract}

\hspace*{0.35cm}{\bf Keywords:} $r$-dynamic coloring, $r$-dynamic
chromatic number, graph\\ \hspace*{0.8cm} operations.

\centerline{}

\section*{Introduction}
We refer all basic definition of graph to a handbook of graph theory
written by Gross {\it et. al} \cite{Gross}. Let $G=(V,E)$ be a
simple, connected and undirected graph with vertex set $V$ and edge
set $E$, and $d(v)$ be a degree of any $v\in V(G)$. The maximum
degree and the minimum degree of $G$ are denoted by $\Delta(G)$ and
$\delta(G)$, respectively. By a proper $k$-coloring  of a graph $G$,
we mean a map $ c : V (G) \rightarrow 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))| \geq 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 \in S\}$ for
a vertex subset $S$. The $r$-dynamic chromatic number, written as
$\chi_r(G)$, is the minimum $k$ such that $G$ has an $r$-dynamic
$k$-coloring. Note that the $1$-dynamic chromatic number of graph is
equal to its chromatic number, denoted by $\chi(G)$, and the
$2$-dynamic chromatic number was introduced by Montgomery
\cite{Mont} under the name a dynamic chromatic number, denoted by
$\chi_d(G)$. He conjectured $\chi_2(G) \leq \chi(G)+2$ when $G$ is
regular, which remains open. Akbari {\it et. al} \cite{Akbari}
proved Montgomery's conjecture for bipartite regular graphs. Lai,
{\it et.al} \cite{Lai} proved $\chi_2(G) \leq \Delta(G)+1$ when
$\Delta(G) \geq 3$ and no component contains $C_5$. Kim {\it et. al}
\cite{Kim2} proved $\chi_2(G) \leq 4$ when $G$ is planar and no
component is $C_5$ and also $\chi_d \leq 5$ whenever $G$ is planar.

Obviously, $\chi(G) \le \chi_2 (G)$, but it was shown in \cite{Lai}
that the difference between the chromatic number and the dynamic
chromatic number can be arbitrarily large. However, it was
conjectured that for regular graphs the difference is at most 2.
Some properties of dynamic coloring were studied in
\cite{Kim2,Akbari,Lai}. It was proved in \cite{Brook} that, for a
connected graph $G$, if $\Delta(G) \le 3$, then $\chi_2(G) \le 4$
unless $G = C_5$, in which case $\chi_2(C_5)=5$ and if $\Delta(G)
\ge 4$ then $\chi (G)\le \Delta + 1$. Considering those results,
finding an exact value of $\chi_r(G)$ is significantly useful  as
there are a little number of results provide an exact value of
$\chi_r(G)$. Thus, in this paper we will show it when $G$ is an
operation of special graphs.


\section*{Some Useful Lemmas}

\hspace{0.6cm}The following lemmas are useful for determining the
dynamic coloring of graphs. Jahanbekam {\it et. al} \cite{Jahan}
characterize the upper bound of $\chi_r(G)$ in term of the diameter
of graph.

\begin{Theor}\label{fff}\cite{Jahan}
If $diam(G) = 2$, then $\chi_2(G) \le  \chi(G) + 2$, with equality
holds only when $G$ is a complete bipartite graph or $C_5$.
\end{Theor}

\begin{Theor}\label{ggg}\cite{Jahan}
If $G$ is a $k$-chromatic graph with diameter at most 3, then
$\chi_2 (G) \le 3k$, and this bound is sharp when $k \ge 2$.
\end{Theor}

In term of the maximum degree of graph, the $r$-dynamic of graph
satisfies as follows

\begin{observation}\label{aaa}\cite{Jahan}
$\chi_r(G) \geq min\{\Delta(G),r\}+1$, and this is sharp. If
$\Delta(G)\le r$ then $\chi_r(G) = min\{\Delta(G),r\}$.
\end{observation}

\begin{Theor}\label{eee}\cite{Jahan}
$\chi_r(G) \le r\Delta(G) +1$, with equality for $r \ge 2$ if and
only if $G$ is $r$-regular with diameter $2$ and girth
$5$.
\end{Theor}

The last for the graph operations,  Jahanbekam {\it et. al} proved
the following theorem.

\begin{Theor}\label{ddd}\cite{Jahan}
If $\delta(G) \ge r$ then $\chi_r(G\Box H) = max\{\chi (G),
\chi(H)\}$.
\end{Theor}

\section*{The Results}
\hspace{0.6cm}Now, we are ready to show our results on $r$-dynamic
coloring for some special graph operations. Apart from showing the
$r$-dynamic chromatic number we also show the colors $c(v\in V(G))$
for clarity. Some graph operations which have been found in this
paper are $P_n+C_m,C_n \Box S_m, C_n \otimes S_m, C_n [S_m],C_n
\odot S_m, shack(P_n\Box C_m,v,s), \newline amal(P_n\Box C_m,v,s)$.

%%%%%%%%%%%%1
\begin{Theor}\label{teotribun}
Let $G$ be a joint $P_n$ and $C_m$. For $n \geq 2$ dan $m \geq 3$,
the $r$-dynamic chromatic number of $G$ is
\begin{displaymath}
\chi(P_n+C_m)=\chi_d(P_n+C_m)=\chi_3(P_n+C_m)= \left\{
\begin{array}{ll}
\ 4, & {\rm for}\,\, $m$\,\, {\rm even} \\
\ 5, & {\rm for}\,\, $m$\,\, {\rm odd}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
\chi_4(P_n+C_m)= \left\{
\begin{array}{ll}
\ 5, & {\rm for}\,\, m\equiv 3({\rm mod\ 3}) \\
\ 6, & {\rm otherwise}\\
\end{array} \right.
\end{displaymath}
\end{Theor}

\hspace*{-0.53cm}{\bf Proof.} The graph $P_n+C_m$ is a connected
graph with vertex set $V(P_n+C_m)$= $\{x_i; 1 \leq i \leq n\}$
$\cup$ $\{y_j; 1 \leq j \leq m\}$ and  $E(P_n+C_m)$= $\{x_i x_{i+1};
1 \leq i \leq n-1\}$ $\cup \{y_j y_{j+1}, y_m y_1; 1 \leq j \leq
m-1\}$ $\cup \{x_i y_j; 1 \leq i \leq n;\ 1 \leq j \leq m\}$. Thus
$p=|V(P_n + C_m)|= n+m, q=|E(G)|= nm+n+m-1$ and $\Delta(P_n +
C_m)=m+2$. By Observation \ref{aaa}, the lower bound of $r$-dynamic
chromatic number  $\chi_r (P_n + C_m)\ge min\{\Delta(P_n +
C_m),r\}+1=\{m+2,r\}+1$.

For $\chi(P_n+C_m)=\chi_d(P_n+C_m)=\chi_3(P_n+C_m)$, define the
vertex colouring $c: V(P_n+C_m) \to \{1,2, \dots, k\}$ for  $n \geq
2$ and $m \geq 3$ as follows:
\begin{displaymath}
c(x_i) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm odd}\\
\ 2,\ 1 \leq i \leq n,\ i\ {\rm even}\\
\end{array} \right.
\hspace*{1cm} c(y_j) = \left\{ \begin{array}{ll}
\ 3,\ 1 \leq j \leq m,\ j\ {\rm odd},\ m \ {\rm even} \\
\ 4,\ 1 \leq j \leq m,\ j\ {\rm even},\ m \ {\rm even} \\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(y_j) = \left\{ \begin{array}{ll}
\ 3,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ m \ {\rm odd} \\
\ 4,\ 1 \leq j \leq m-2,\ j\ {\rm even},\ m \ {\rm odd} \\
\ 5,\ j= m,\ m \ {\rm odd} \\
\end{array} \right.
\end{displaymath}

It is easy to see that $c: V(P_n+C_m) \to \{1,2, \dots, 4\}$ and $c:
V(P_n+C_m) \to \{1,2, \dots, 5\}$, for $m$ even and odd
respectively, are proper coloring. Thus, $\chi(P_n+C_m)=4$ and
$\chi(P_n+C_m)=5$, for $m$ even and odd respectively. By definition,
since $min\{|c(N(v))|, \,\,{\rm for\, every}\,\, v\in
V(P_n+C_m)\}=3\le \delta(P_n + C_m)=4$, it implies
$\chi(P_n+C_m)=\chi_d(P_n+C_m)=\chi_3(P_n+C_m)$.

For $\chi_4(P_n+C_m)$, define the vertex colouring $c: V(P_n+C_m)
\to \{1,2, \dots, k\}$ for  $n \geq 2$ and $m \geq 3$ as follows:
\\
For $m\equiv 3\ ({\rm mod\ 3})$
\begin{displaymath}
c(x_i) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm odd}\\
\ 2,\ 1 \leq i \leq n,\ i\ {\rm even}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(y_j) = \left\{ \begin{array}{ll}
\ 3,\ 1 \leq j \leq m,\ j\equiv 5\ ({\rm mod\ 3})\\
\ 4,\ 1 \leq j \leq m,\ j\equiv 4\ ({\rm mod\ 3})\\
\ 5,\ 1 \leq j \leq m,\ j\equiv 3\ ({\rm mod\ 3})\\
\end{array} \right.
\end{displaymath}
For $m\equiv 4\ ({\rm mod\ 3})$
\begin{displaymath}
c(x_i) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm odd}\\
\ 2,\ 1 \leq i \leq n,\ i\ {\rm even}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(y_j) = \left\{ \begin{array}{ll}
\ 3,\ 1 \leq j \leq m-1,\ j\equiv 5\ ({\rm mod\ 3})\\
\ 4,\ 1 \leq j \leq m-1,\ j\equiv 4\ ({\rm mod\ 3})\\
\ 5,\ 1 \leq j \leq m-1,\ j\equiv 3\ ({\rm mod\ 3})\\
\ 6,\ j=m\\
\end{array} \right.
\end{displaymath}
For $m\equiv 5\ ({\rm mod\ 3})$
\begin{displaymath}
c(x_i) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\equiv 5\ ({\rm mod\ 3})\\
\ 2,\ 1 \leq i \leq n,\ i\equiv 4\ ({\rm mod\ 3})\\
\ 3,\ 1 \leq i \leq n,\ i\equiv 3\ ({\rm mod\ 3})\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(y_j) = \left\{ \begin{array}{ll}
\ 4,\ 1 \leq j \leq m,\ j\ {\rm odd},\ m \ {\rm even} \\
\ 5,\ 1 \leq j \leq m,\ j\ {\rm even},\ m \ {\rm even} \\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(y_j) = \left\{ \begin{array}{ll}
\ 4,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ m \ {\rm odd} \\
\ 5,\ 1 \leq j \leq m-2,\ j\ {\rm even},\ m \ {\rm odd} \\
\ 6,\ j= m,\ m \ {\rm odd} \\
\end{array} \right.
\end{displaymath}

It is easy to see, for $m\equiv 3\ ({\rm mod\ 3})$ $c: V(P_n+C_m)
\to \{1,2, \dots, 5\}$, and otherwise $c: V(P_n+C_m) \to \{1,2,
\dots, 6\}$ are proper coloring. Thus, for $m\equiv 3\ ({\rm mod\
3})$, $\chi_4(P_n+C_m)=5$ and $\chi(P_n+C_m)=6$ otherwise. By
definition, since $min\{|c(N(v))|, \,\,{\rm for\, every}\,\, v\in
V(P_n+C_m)\}=4\le \delta(P_n + C_m)=4$, it is proved that
$\chi_4(P_n+C_m)=5$.\ebox

\begin{openproblem}\label{teotribun}
Let $G$ be a joint $P_n$ and $C_m$. For $n \geq 2$ and $m \geq 3$,
determine the $r$-dynamic chromatic number of $G$  when $r\ge 5$.
\end{openproblem}

%%%%%%%%%%%%%2
\begin{Theor}
Let $G$ be a cartesian product of $C_n$ and $S_m$. For $n \geq 3$
dan $m \geq 3$, the $r$-dynamic chromatic number of $G$ is
\begin{displaymath}
\chi(C_n \Box S_m)= \left\{ \begin{array}{ll}
\ 2, & for\,\, $n$\,\, $even$ \\
\ 3, & $for$\,\, $n$\,\, $odd$\\
\end{array} \right.
\end{displaymath}
\end{Theor}

\hspace*{-0.53cm}{\bf Proof.} The graph $C_n \Box S_m$ is a
connected graph with vertex set $V(C_n \Box S_m)$=  $\{A_{i}; 1 \leq
i \leq n\}$ $\cup \{x_{i,j}; 1 \leq i \leq n;\ 1 \leq j \leq m\}$
and $E(C_n \Box S_m)$= $\{A_{i} A_{i+1};\ 1 \leq i \leq n-1\}$ $\cup
\{A_{n} A_{1}\}$ $\cup \{x_{i,j} x_{i+1,j};\ 1 \leq i \leq n-1; 1
\leq j \leq m\}$ $\cup \{x_{n,j} x_{1,j};\ 1 \leq j \leq m\}$ $\cup
\{A_{i} x_{i,j}; 1 \leq i \leq n;\ 1 \leq j \leq m\}$. Thus $|V(C_n
\Box S_m)|= nm+n$ and $|E(C_n \Box S_m)|= 2nm+n$ and $\Delta(C_n
\Box S_m)=5$. By Observation \ref{aaa}, the lower bound of
$r$-dynamic chromatic number  $\chi_r (C_n \Box S_m)\ge
min\{\Delta(C_n \Box S_m),r\}+1=\{5,r\}+1$. Define the vertex
colouring $c: V(C_n \Box S_m) \to \{1,2, \dots, k\}$ for $n \geq 3$
and $m \geq 3$ as follows:

\hspace{-0.6cm}For $n$ even
\begin{displaymath}
c(A_{i}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm odd}\\
\ 2,\ 1 \leq i \leq n,\ i\ {\rm even}\\
\end{array} \right.,
\hspace{0.5cm} c(x_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm even}, 1 \leq j \leq m\\
\ 2,\ 1 \leq i \leq n,\ i\ {\rm odd}, 1 \leq j \leq m\\
\end{array} \right.
\end{displaymath}

\hspace{-0.6cm}For $n$ odd
\begin{displaymath}
c(A_{i}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n-2,\ i\ {\rm odd}\\
\ 2,\ 1 \leq i \leq n-1,\ i\ {\rm even}\\
\ 3,\ i= n\\
\end{array} \right.,
\hspace{0.1cm} c(x_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 2 \leq i \leq n,\ i\ {\rm even}, 1 \leq j \leq m\\
\ 2,\ 2 \leq i \leq n,\ i\ {\rm odd}, 1 \leq j \leq m\\
\ 3,\ i= 1\\
\end{array} \right.
\end{displaymath}

It is easy to see that $c: V(C_n \Box S_m) \to \{1,2\}$ and $c:
V(C_n \Box S_m) \to \{1,2,3\}$, for $n$ even and odd respectively,
is proper coloring. By definition, since $min\{|c(N(v))|,\newline
\,\,{\rm for\, every}\,\, v\in V(P_n\Box C_m)\}=1\le \delta(C_n \Box
S_m)=3$,  thus we only have $\chi(C_n \Box S_m)=2$ and $\chi(C_n
\Box S_m)=3$, for $n$ even and odd respectively.\ebox

\begin{openproblem}\label{teotribun}
Let $G$ be a cartesian product of $C_n$ and $S_m$. For $n \geq 3$
and $m \geq 3$, determine the $r$-dynamic chromatic number of $G$
when $r\ge 2$.
\end{openproblem}

%%%%%%%%%%%%%3
\begin{Theor}
Let $G$ be a tensor product of $C_n$ and $S_m$. For $n \geq 3$ dan
$m \geq 3$, the $r$-dynamic chromatic number of $G$ is $\chi(C_n
\otimes S_m)= 2$
\end{Theor}

\hspace*{-0.53cm}{\bf Proof.} The graph $C_n \otimes S_m$ is a
connected graph with vertex set $V$= $\{A_{i}; 1 \leq i \leq n\}$
$\cup \{x_{i,j}; 1 \leq i \leq n\; 1 \leq j \leq m\}$ dan  $E$=
$\{A_{i} x_{i+1,j}; 1 \leq i \leq n-1; 1 \leq j \leq m\}$ $\cup
\{A_{i} x_{i-1,j}; 2 \leq i \leq n; 1 \leq j \leq m\}$ $\cup \{A_{1}
x_{n,j}; 1 \leq j \leq m\}$ $\cup \{A_{n} x_{1,j}; 1 \leq j \leq
m\}$. Thus $|V(C_n \otimes S_m)|= nm+n$ and $|E(C_n \otimes S_m)|=
2nm$ and $\Delta(C_n \otimes S_m)=2m$. By Observation \ref{aaa}, the
lower bound of $r$-dynamic chromatic number  $\chi_r (C_n \otimes
S_m)\ge min\{\Delta(C_n \otimes S_m),r\}+1=\{2m,r\}+1$. Define the
vertex colouring $c: V(C_n \otimes S_m) \to \{1,2, \dots, k\}$ for
$n \geq 3$ and $m \geq 3$ as follows:
\begin{eqnarray*}
c(A_{i})&=& 1,\,\, 1 \leq i \leq n\\
c(x_{i,j})&=& 2,\,\, 1 \leq i \leq n;\ 1 \leq j \leq m
\end{eqnarray*}

It is easy to see that $c: V(C_n \otimes S_m) \to \{1,2\}$ is proper
coloring. By definition, since $min\{|c(N(v))|,\,\,{\rm for\,
every}\,\, v\in V(P_n\Box C_m)\}=1\le \delta(C_n \otimes S_m)=2$,
thus we only have $\chi(C_n \otimes S_m)=2$.\ebox

\begin{openproblem}\label{teotribun}
Let $G$ be a cartesian product of $C_n$ and $S_m$. For $n \geq 3$
and $m \geq 3$, determine the $r$-dynamic chromatic number of $G$
when $r\ge 2$.
\end{openproblem}

%%%%%%%%%%%%%4
\begin{Theor}
Let $G$ be a composition of graph $C_n$ on $S_m$. For $n \geq 3$ dan
$m \geq 3$, the $r$-dynamic chromatic number of $G$ is
\begin{displaymath}
\chi(C_n[S_m])=\chi_d(C_n[S_m])=\chi_3(C_n[S_m])= \left\{
\begin{array}{ll}
\ 4,\ $for$\ $n$\ $even$ \\
\ 6,\ $for$\ $n$\ $odd$\\
\end{array} \right.
\end{displaymath}
\end{Theor}

\hspace*{-0.53cm}{\bf Proof.} The graph $C_n [S_m]$ is a connected
graph with vertex set $V(C_n [S_m])$= $\{A_{i}; 1 \leq i \leq n\}$
$\cup \{x_{i,j}; 1 \leq i \leq n\; 1 \leq j \leq m\}$ and  $E(C_n
[S_m])$= $\{A_{i} A_{i+1};\ 1 \leq i \leq n-1\}$ $\cup \{A_{n}
A_{1}\}$ $\cup \{x_{i,j} x_{i+1,j};\ 1 \leq i \leq n-1; 1 \leq j
\leq m\}$ $\cup \{x_{n,j} x_{1,j};\ 1 \leq j \leq m\}$ $\cup \{A_{i}
x_{i,j}; 1 \leq i \leq n; 1 \leq j \leq m\}$ $\cup \{A_{i}
x_{i+1,j}; 1 \leq i \leq n-1; 1 \leq j \leq m\}$ $\cup \{A_{i}
x_{i-1,j}; 2 \leq i \leq n; 1 \leq j \leq m\}$ $\cup \{A_{1}
x_{n,j}; 1 \leq j \leq m\}$ $\cup \{A_{n} x_{1,j}; 1 \leq j \leq
m\}$. Thus $|V(C_n[S_m])|= nm + n$ and $|E(C_n[S_m])|= 4nm+n$ and
$\Delta(C_n [S_m])=3m+2$. By Observation \ref{aaa}, the lower bound
of $r$-dynamic chromatic number  $\chi_r (C_n[S_m])\ge
min\{\Delta(C_n[S_m]),r\}+1=\{3m+2,r\}+1$. Define the vertex
colouring $c: V(C_n[S_m]) \to \{1,2, \dots, k\}$ for $n \geq 3$ and
$m \geq 3$ as follows:

\begin{displaymath}
c(A_i) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm odd} \\
\ 2,\ 1 \leq i \leq n,\ i\ {\rm even}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x_{i,j}) = \left\{ \begin{array}{ll}
\ 3,\ 1 \leq i \leq n,\ i\ {\rm odd};\ 1 \leq j \leq m\  {\rm and} \ n \ {\rm even}\\
\ 4,\ 1 \leq i \leq n,\ i\ {\rm odd};\ 1 \leq j \leq m\  {\rm and} \ n \ {\rm even}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x_{i,j}) = \left\{ \begin{array}{ll}
\ 3,\ 1 \leq i \leq n-2,\ i\ {\rm odd};\ 1 \leq j \leq m\  {\rm and} \ n \ {\rm odd}\\
\ 4,\ 1 \leq i \leq n-1,\ i\ {\rm odd};\ 1 \leq j \leq m\  {\rm and} \ n \ {\rm odd}\\
\ 5,\ i=n\\
\end{array} \right.
\end{displaymath}

It is easy to see that $c: V(C_n[S_m]) \to \{1,2, \dots, 4\}$ and
$c: V(C_n[S_m]) \to \{1,2, \dots, 5\}$, for $n$ even and odd
respectively, is proper coloring. Thus, $\chi(C_n[S_m])=4$ and
$\chi(C_n[S_m])=5$, for $n$ even and odd respectively. By
definition, since $min\{|c(N(v))|,\newline \,\,{\rm for\, every}\,\,
v\in V(C_n[S_m])\}=3\le \delta(C_n [S_m])=5$, it implies
$\chi(C_n[S_m])=\chi_d(C_n[S_m])=\chi_3(C_n[S_m])$. It completes the
proof.\ebox

\begin{openproblem}\label{teotribun}
Let $G$ be a cartesian product of $C_n$ and $S_m$. For $n \geq 3$
and $m \geq 3$, determine the $r$-dynamic chromatic number of $G$
when $r\ge 4$.
\end{openproblem}

%%%%%%%%%%%%%5
\begin{Theor}
Let $G$ be a crown product of $C_n$ on $S_m$. For $n \geq 3$ dan $m
\geq 3$, the $r$-dynamic chromatic number of $G$ is
\begin{displaymath}
\chi(C_n \odot S_m)= \chi_d(C_n \odot S_m)=\left\{ \begin{array}{ll}
\ 3,\ {\rm for}\ $n$\ {\rm even} \\
\ 4,\ {\rm for}\ $n$\ {\rm odd}\\
\end{array} \right.
\end{displaymath}
\end{Theor}

\hspace*{-0.53cm}{\bf Proof.} The graph $C_n \odot S_m$ is a
connected graph with vertex set $V(C_n \odot S_m)$= $\{A \}$ $\cup
\{x_j; 1 \leq j \leq m \}$ $\cup \{y_i; 1 \leq i \leq n \}$ $\cup
\{y_{i,j}; 1 \leq i \leq n; 1 \leq j \leq m \}$ and  $E(C_n \odot
S_m)$= $\{A x_{j}; 1 \leq j \leq m\}$ $\cup \{A y_{i}; 1 \leq i \leq
n\}$ $\cup \{x_{j} y_{i,j}; 1 \leq i \leq n; 1 \leq j \leq m \}$
$\cup \{y_{i} y_{i+1}; 1 \leq i \leq n-1\}$ $\cup \{y_{n} y_{1} \}$
$\cup \{y_{i,j} y_{i+1,j}; 1 \leq i \leq n-1; 1 \leq j \leq m\}$
$\cup \{y_{n,j} y_{1,j}; 1 \leq j \leq m\}$. Thus $|V(C_n[S_m])|=
nm+n+m+1$ and $|E(C_n \odot S_m)|= 2nm +m+2n$ and $\Delta(C_n \odot
S_m)=m+n$. By Observation \ref{aaa}, the lower bound of $r$-dynamic
chromatic number  $\chi_r (C_n \odot S_m)\ge min\{\Delta(C_n \odot
S_m),r\}+1=\{m+n,r\}+1$. Define the vertex colouring $c: V(C_n \odot
S_m) \to \{1,2, \dots, k\}$ for $n \geq 3$ and $m \geq 3$ as
follows: $A = 1, c(x_{j}) = 2, \ 1 \leq j \leq m$ and

\hspace*{-0.5cm}For $n$ even
\begin{displaymath}
c(y_{i}) = \left\{ \begin{array}{ll}
\ 2,\ 1 \leq i \leq n,\ i\ {\rm odd}\\
\ 3,\ 1 \leq i \leq n,\ i\ {\rm even}\\
\end{array} \right.;\,\,
c(y_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm odd}, 1 \leq j \leq m\\
\ 3,\ 1 \leq i \leq n,\ i\ {\rm even}, 1 \leq j \leq m\\
\end{array} \right.
\end{displaymath}

\hspace*{-0.5cm}For $n$ odd
\begin{displaymath}
c(y_{i}) = \left\{ \begin{array}{ll}
\ 2,\ 1 \leq i \leq n-2,\ i\ {\rm odd}\\
\ 3,\ 1 \leq i \leq n-1,\ i\ {\rm even}\\
\ 4,\ i = n\\
\end{array} \right.;\,\,
c(y_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq n,\ i\ {\rm odd}, 1 \leq j \leq m\\
\ 3,\ 1 \leq i \leq n,\ i\ {\rm even}, 1 \leq j \leq m\\
\ 4,\ i = n\\
\end{array} \right.
\end{displaymath}

It is easy to see that $c: V(C_n \odot S_m) \to \{1,2, \dots, 3\}$
and $c: V(C_n \odot S_m) \to \{1,2, \dots, 4\}$, for $n$ even and
odd respectively, is proper coloring. Thus, $\chi(C_n \odot S_m)=3$
and $\chi(C_n \odot S_m)=4$, for $n$ even and odd respectively. By
definition, since $min\{|c(N(v))|,\,\,{\rm for\, every}\,\, v\in
V(C_n \odot S_m)\}=2\le \delta(C_n \odot S_m)=3$, it implies
$\chi(C_n \odot S_m)=\chi_d(C_n \odot S_m)$. It completes the
proof.\ebox

\begin{openproblem}\label{teotribun}
Let $G$ be a crown product of $C_n$ on $S_m$. For $n \geq 3$ dan $m
\geq 3$, determine the $r$-dynamic chromatic number of $G$ when
$r\ge 3$.
\end{openproblem}

%%%%%%%%%%%%%
\begin{Theor}
Let $G$ be a shackle of cartesian product $P_n$ and $C_m$. For $n
\geq 2$ and $m \geq 3$, the $r$-dynamic chromatic number of $G$ is
\begin{displaymath}
\chi(shack(P_n\Box C_m,v,s))= \chi_d(shack(P_n\Box C_m,v,s))=\left\{
\begin{array}{ll}
\ 3,\ {\rm for}\ $n$\ {\rm even} \\
\ 4,\ {\rm for}\ $n$\ {\rm odd}\\
\end{array} \right.
\end{displaymath}
\end{Theor}

\hspace*{-0.53cm}{\bf Proof.} The shackle of cartesian product $P_n$
and $C_m$, denoted by $shack(P_n\Box C_m,v,s)$, is a connected graph
with vertex set $V$= $\{x^{k}_{i,j}; 1 \leq i \leq n;\ 1 \leq j \leq
m;\ 1 \leq k \leq s\}$ $\cup \{x^{k}_{n,j}; 1 \leq j \leq m;\ 1 \leq
k \leq s\}$ $\cup \{x^{r}_{n,j}; 1 \leq j \leq m\}$ dan $E$=
$\{x^{k}_{i,j} x^{k}_{i,j+1}; 1 \leq i \leq n;\ 1 \leq j \leq m-1;\
1 \leq k \leq s\}$ $\cup \{x^{k}_{i,m} x^{k}_{i,1}; 1 \leq i \leq
n;\ 1 \leq k \leq s\}$ $\cup \{x^{k}_{i,j} x^{k}_{i+1,j};1 \leq i
\leq n;\ 1 \leq j \leq m;\ 1 \leq k \leq s\}$. Thus
$|V(shack(P_n\Box C_m,v,s))|= nms-s + 1$ and $|E(shack(P_n\Box
C_m,v,s))|= 2nms-ns$ and $\Delta(shack(P_n\Box C_m,v,s))=6$. By
Observation \ref{aaa}, the lower bound of $r$-dynamic chromatic
number  $\chi_r (shack(P_n\Box C_m,v,s))\ge
min\{\Delta(shack(P_n\Box C_m,v,s)),r\}+1=\{6,r\}+1$. Define the
vertex colouring $c: V(shack(P_n\Box C_m,v,s)) \to \{1,2, \dots,
k\}$ for $n \geq 3$ and $m \geq 3$ as follows:

\hspace*{-0.5cm}For $m$ {\rm even}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ k\ {\rm odd}\ {\rm and}\ i\ {\rm odd}\\
\ 2,\ 1 \leq j \leq m,\ j\ {\rm even},\ k\ {\rm odd}\ {\rm and}\ i\ {\rm odd}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m,\ j\ {\rm even},\ k\ {\rm odd}\ {\rm and}\ i\ {\rm even}\\
\ 2,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ k\ {\rm odd}\ {\rm and}\ i\ {\rm even}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ k\ {\rm odd}\ {\rm and}\ i=n\\
\ 2,\ 1 \leq j \leq m-1,\ j\ {\rm even},\ k\ {\rm odd}\ {\rm and}\ i=n\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-1,\ j\ {\rm even},\ k\ {\rm even}\ {\rm and}\ i\ {\rm odd}\\
\ 2,\ 1 \leq j \leq m,\ j\ {\rm odd},\ k\ {\rm even}\ {\rm and}\ i\ {\rm odd}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ k\ {\rm even}\ {\rm and}\ i\ {\rm even}\\
\ 2,\ 1 \leq j \leq m,\ j\ {\rm even},\ k\ {\rm even}\ {\rm and}\ i\ {\rm even}\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-1,\ j\ {\rm even},\ k\ {\rm even}\ {\rm and}\ i=n\\
\ 2,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ k\ {\rm even}\ {\rm and}\ i=n\\
\end{array} \right.
\end{displaymath}

For $m$ odd
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-2,\ j\ {\rm even},\ k\ {\rm even}\ {\rm and}\ i\ {\rm odd}\\
\ 2,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ k\ {\rm even}\ {\rm and}\ i\ {\rm odd}\\
\ 3,\ j=m
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-2,\ j\ {\rm odd},\ k\ {\rm odd}\ {\rm and}\ i\ {\rm even}\\
\ 2,\ 1 \leq j \leq m-1,\ j\ {\rm even},\ k\ {\rm odd}\ {\rm and}\ i\ {\rm even}\\
\ 3,\ j=m
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq j \leq m-2,\ j\ {\rm even},\ k\ {\rm odd}\ {\rm and}\ i=n\\
\ 2,\ 1 \leq j \leq m-1,\ j\ {\rm odd},\ k\ {\rm odd}\ {\rm and}\ i=n\\
\ 3,\ j=m
\end{array} \right.
\end{displaymath}

It is easy to see that $c: V(shack(P_n\Box C_m,v,s)) \to \{1,2\}$
and $c: V(C_n \odot S_m) \to \{1,2,3\}$, for $m$ even and odd
respectively, are proper coloring. Thus, $\chi(shack(P_n\Box
C_m,v,s))=2$ and $\chi(shack(P_n\Box C_m,v,s))=3$, for $m$ even and
odd respectively. By definition, since $min\{|c(N(v))|,\,\,{\rm
for\, every}\,\, v\in V(shack(P_n\Box C_m,v,s)\}\newline =1\le
\delta(shack(P_n\Box C_m,v,s))=3$, thus we only have $\chi(shack(P_n
\Box C_m))=2$ and $\chi(shack(P_n\Box C_m,v,s))=3$, for $m$ even and
odd respectively. It completes the proof.\ebox

\begin{openproblem}\label{teotribun}
Let $G$ be a shackle of cartesian product $P_n$ and $C_m$. For $n
\geq 2$ and $m \geq 3$, determine the $r$-dynamic chromatic number
of $G$ when $r\ge 2$.
\end{openproblem}

%%%%%%%%%%%%%
\begin{Theor}
Let $G$ be an amalgamation of cartesian product $P_n$ and $C_m$. For
$n \geq 2$ and $m \geq 3$, the $r$-dynamic chromatic number of $G$
is
\begin{displaymath}
\chi (Amal(P_{n} \Box C_m, v, s))= \left\{ \begin{array}{ll}
\ 2,\ {\rm for}\ $m$\ {\rm even}\\
\ 3,\ {\rm for}\ $m$\ {\rm odd}\\
\end{array} \right.
\end{displaymath}
\end{Theor}

\hspace*{-0.53cm}{\bf Proof.} Amalgamation  of cartesian product
$P_n$ and $C_m$, denoted by $amal(P_n\Box C_m,v,s)$, is a connected
graph with vertex set $V(amal(P_n\Box C_m,v,s))$= $\{A, x^{k}_{i,j};
1 \leq i \leq m;\ 1 \leq j \leq n\}$ and  $E(amal(P_n\Box
C_m,v,s))$= $\{A x^{k}_{1,n}, A x^{k}_{m-1,n};1 \leq k \leq s\}$
$\cup \{x^{k}_{i,n} x^{k}_{i+1,n}$ $\cup \{x^{k}_{i,j}
x^{k}_{i+1,j}; 1 \leq i \leq m-1;\ 1 \leq j \leq n-1;\ 1 \leq k \leq
s\}$ $\cup \{x^{k}_{n,j} x^{k}_{1,j}; 1 \leq j \leq n-1;\ 1 \leq i
\leq m;\ 1 \leq k \leq s\}$ $\cup \{x^{k}_{i,j} x^{k}_{i,j+1}; 1
\leq j \leq n-1; 1 \leq i \leq m;\ 1 \leq k \leq s\}$. Thus
$|V(amal(P_n\Box C_m,v,s))|= 1+(nm-1)s$ and $|E(amal(P_n\Box
C_m,v,s))|= (2nm-m)s$ and $\Delta(amal(P_n\Box C_m,v,s))=3s$. By
Observation \ref{aaa}, the lower bound of $r$-dynamic chromatic
number  $\chi_r (amal(P_n\Box C_m,v,s))\ge min\{\Delta(amal(P_n\Box
C_m,v,s)),r\}+1=\{3s,r\}+1$. Define the vertex colouring $c:
V(amal(P_n\Box C_m,v,s)) \to \{1,2, \dots, k\}$ for $n \geq 3$ and
$m \geq 3$ as follows: $c(A)=1$ and

For $m$ even
\begin{displaymath}
c(x^{k}_{i,n}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq m-2,\ i\ {\rm even};\ 1 \leq k \leq s\\
\ 2,\ 1 \leq i \leq m-1,\ i\ {\rm odd};\ 1 \leq k \leq s\\
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq m,\ i\ {\rm even};\ 1 \leq j \leq l;\ 1 \leq k \leq s\\
\ 2,\ 1 \leq i \leq m-1,\ i\ {\rm odd}\\
\end{array} \right.
\end{displaymath}

For $m$ odd
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq m-2,\ i\ {\rm even};\ 1 \leq k \leq s, \ j\ {\rm odd} \\
\ 2,\ 1 \leq i \leq m-2,\ i\ {\rm odd};\ 1 \leq k \leq s, \ j\ {\rm odd} \\
\ 3,\ i= m-1
\end{array} \right.
\end{displaymath}
\begin{displaymath}
c(x^{k}_{i,j}) = \left\{ \begin{array}{ll}
\ 1,\ 1 \leq i \leq m-1,\ i\ {\rm even};\ 1 \leq k \leq s, \ j\ {\rm even} \\
\ 2,\ 1 \leq i \leq m-1,\ i\ {\rm odd};\ 1 \leq k \leq s, \ j\ {\rm even} \\
\ 3,\ i= m
\end{array} \right.
\end{displaymath}

Clearly $c: V(amal(P_n\Box C_m,v,s)) \to \{1,2\}$ and $c:
V(amal(P_n\Box C_m,v,s)) \to \{1,2,3\}$, for $m$ even and odd
respectively, are proper coloring. Thus, for $m$ even,
$\chi(amal(P_n\Box C_m,v,s)) =2$ and for $m$ odd, $\chi(amal(P_n\Box
C_m,v,s))=3$. By definition, since $min\{|c(N(v))|,\,\,{\rm for\,
every}\,\, v\in V(amal(P_n\Box C_m,v,s)\}=1\le \delta(amal(P_n\Box
C_m,v,\newline s))=3$, thus we only have $\chi(amal(P_n\Box
C_m,v,s))=2$ and $\chi(amal(P_n\Box C_m,v,s))=3$, for $m$ even and
odd respectively. It completes the proof.\ebox

\begin{openproblem}\label{teotribun}
Let $G$ be a shackle of cartesian product $P_n$ and $C_m$. For $n
\geq 2$ and $m \geq 3$, determine the $r$-dynamic chromatic number
of $G$ when $r\ge 2$.
\end{openproblem}

\section*{Conclusions}
We have studied the $r$-dynamic coloring of some graph operations.
The results show for each graph operation we have not obtained
completely all values of $r$, therefore we left as the above open
problems for the further study.


%++++++++++++++++++++++++++++++++++++++++++++++++++++++++
%Reference
%++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\renewcommand{\baselinestretch}{1.5}
\begin{thebibliography}{99}

\bibitem{Gross} J.L. Gross, J. Yellen and P. Zhang, \textit{ Handbook of Graph
Theory}, Second Edition, CRC Press, Taylor and Francis Group, 2014

\bibitem{Kim1} S.J. Kim and W.J. Park, List dynamic coloring of sparse graphs,
{\it Combinatorial optimization and applications. Lect. Notes
Comput. Sci.} 6831 (Springer, 2011), 156– 162.

\bibitem{Kim2} S.J. Kim, S. J. Lee, and W.J. Park, Dynamic coloring and list
dynamic coloring of planar graphs. {\it Discrete Applied Math.} 161
(2013), 2207–2212.

\bibitem{Akbari} S. Akbari, M. Ghanbari, S. Jahanbekam, On the dynamic chromatic
number of graphs, {\it Combinatorics and graphs. Contemp. Math.} 531
(Amer. Math. Soc. 2010), 1–18.

\bibitem{Mont} B. Montgomery, Dynamic Coloring of Graphs. {\it Ph.D
Dissertation}, West Virginia University, 2001.

\bibitem{Lai} H.J. Lai, B. Montgomery, and H. Poon, Upper bounds of dynamic
chromatic number. Ars Combin. 68 (2003), 193–201.

\bibitem{Jahan} S Jahanbekam, J Kim, O Suil, D.B. West, On r-dynamic Coloring of
Graphs, 2014, In Press

\bibitem{Brook} R.L. Brooks, On colouring the nodes of a network. Proc.
Cambridge Philos. Soc. 37 (1941), 194–197.

\end{thebibliography}

\end{document}

\end{document}