\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P56}{19(4)}{2012}
\usepackage{amsmath,amssymb,}
\def\thefootnote{\fnsymbol{footnote}}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{sub}{Sublemma}[section]
\newtheorem{example}{Example}[section]
\newtheorem{defin}{Definition}[section]
\newenvironment{definition}{\begin{defin} \rm}{\end{defin}}
\newtheorem{remark}{Remark}[section]
\newenvironment{re}{\begin{remark} \rm}{\end{remark}}
\newenvironment{eg}{\begin{example} \rm}{\end{example}}
\newcommand{\remarks}{\vspace{2ex}\noindent{\bf Remarks.\quad}}
\newcommand{\cremarks}{\vspace{2ex}\noindent{\bf Concluding Remarks.\quad}}
\newcommand{\note}{\vspace{2ex}\noindent{\bf Note.\quad}}
\newcommand{\proof}{{\it Proof.\quad}}
\newcommand{\qed}{\hfill\Box\medskip}
\newcommand{\G}{\Gamma}
\usepackage{CJK}
\begin{document}
\begin{CJK*}{GBK}{song}

%
\newcommand{\be}{\begin{equation}\label}
\newcommand{\ee}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray}\label}
\newcommand{\eea}{\end{eqnarray}}
%




\title{\bf Identifying codes of\\ lexicographic product of graphs}

\author{Min Feng\qquad Min Xu\qquad Kaishun Wang\thanks{Corresponding author.}\\
\small Sch. Math. Sci. {\rm \&} Lab. Math. Com.
Sys.\\[-0.8ex]
\small  Beijing Normal University, Beijing 100875,  China\\
\small \texttt{fengmin@mail.bnu.edu.cn\quad \{xum,wangks\}@bnu.edu.cn}\\
 }

\date{\dateline{Jun 26, 2011}{Dec 13, 2012}{Dec 31, 2012}\\
\small Mathematics Subject Classifications: 94A29, 05C90}


 \maketitle

\begin{abstract}
Let $G$ be a connected graph and $H$ be an arbitrary graph.
 In this  paper, we study the identifying codes of the lexicographic product
 $G[H]$  of  $G$ and $H$.
We first introduce two parameters of $H$, which are closely related
to identifying codes of $H$. Then we provide the sufficient and
necessary condition for $G[H]$ to be identifiable. Finally, if
$G[H]$ is identifiable, we determine the minimum cardinality of
identifying codes of $G[H]$ in terms of the order of $G$ and these
two parameters of $H$.

\medskip
\noindent {\bf Key words:} identifying code; lexicographic product.
\end{abstract}

\section{Introduction}
In this paper, we only consider finite undirected simple graphs with
at least two vertices. For a given graph $G$, we often write $V(G)$
for the vertex set of $G$ and $E(G)$ for the edge set of $G$. For
any two vertices $u$ and $v$ of $G$, let $d_{G}(u,v)$ denote  the
distance between $u$ and $v$ in $G$. Given a vertex $v\in V(G)$,
define $B_{G}(v)=\{u|u\in V(G),d_G(u,v)\leq 1\}$. A \emph{code} $C$
is a nonempty set of vertices. We say that a code $C$ \emph{covers}
$v$ if $B_{G}(v)\cap C\neq\emptyset$; we say that $C$
\emph{separates} two distinct vertices $x$ and $y$ if $B_{G}(x)\cap
C\neq B_{G}(y)\cap C$. An \emph{identifying code} of $G$ is a code
which covers all the vertices of $G$ and separates any pair of
distinct vertices of $G$.
 If $G$ admits at least one identifying code, we say $G$ is \emph{identifiable} and denote
 the minimum cardinality of all identifying codes of $G$ by $I(G)$.

The concept of identifying codes was  introduced by Karpovsky et al.
\cite{Ka1} to model a fault-detection problem in multiprocessor
systems.  It was noted in \cite{Ch,Coh} that determining the
identifying code with the minimum cardinality in a graph is an
NP-complete problem. Many researchers  have focused on the study of
identifying codes in some restricted classes of graphs, for example,
paths \cite{Be}, cycles \cite{Be,Gr,Xu}, hypercubes
\cite{Bl1,Ho,Ka2,Mo} and infinite grids \cite{ben,coh2,ho}.





Gravier et  al. \cite{Gra} investigated  the identifying codes of
Cartesian product of two cliques. Rall and Wash \cite{r} studied the
identifying codes of the direct product of two cliques. In this
paper, we study the identifying codes of the lexicographic product
$G[H]$ of a connected graph $G$ and an arbitrary graph $H$. In
Section 2, we introduce two parameters of a graph which are closely
related to identifying codes, and compute these two parameters of
the path $P_n$ and the cycle $C_n$, respectively. In Section 3, we
first provide the sufficient and necessary condition for $G[H]$ to
be identifiable, then determine $I(G[H])$   in terms of the order of
$G$ and the two parameters of $H$ when $G[H]$ is identifiable. In
particular,  the values of $I(G[P_n])$ and $I(G[C_n])$ are
determined.







\section{Two  parameters}


For  a graph $H$, let $C'\subseteq V(H)$ be a code which separates
any pair of distinct vertices of $H$, we use $I'(H)$ to denote the
minimum cardinality of all possible $C'$. This code was studied in
\cite{Bl1}. Let $C''\subseteq V(H)$ be a code which separates any
pair of distinct vertices of $H$ and satisfies $C''\not\subseteq
B_{H}(v)$ for every $v\in V(H)$, we use $I''(H)$ to denote the
minimum cardinality of all possible $C''$.


The two parameters $I'(H)$ and $I''(H)$ are used to compute the
minimum cardinality of identifying codes of $G[H]$ of graphs $G$ and
$H$  (see Theorem~\ref{main}). In this section we shall compute the
two parameters for  paths and  cycles, respectively.


Given an integer $n\geq 3$, suppose
 $$\begin{array}{c}
V(P_{n})=\{0,1,\ldots,n-1\},\;
 E(P_{n})=\{ij|j=i+1,i=0,\ldots,n-2\};\\
 V(C_{n})=\mathbb{Z}_{n}=\{0,1,\ldots,n-1\},\; E(C_{n})=\{ij|j=i+1,i\in \mathbb{Z}_{n}\}.
\end{array}$$

\begin{example}\rm  $I'(P_{3})=2$ and $I''(P_{3})$ is not well defined; $I'(P_{4})=3$
and $I''(P_{4})=4$; $I'(P_{5})=I''(P_{5})=3$; $I'(P_{6})=3$ and
$I''(P_{6})=4$.

For $P_{4}$, $\{0,1,2\}$ is an identifying code, but
$\{0,1,2\}\subseteq B_{P_{4}}(1)$ and $\{0,1,3\}$ can not separate
$0$ and $1$. For $P_{5}$, $\{0,2,4\}$ separates any pair of distinct
vertices. For $P_{6}$, $\{1,2,3\}$ separates any pair of distinct
vertices, but  $\{1,2,3\}\subseteq B_{P_{6}}(2)$.
\end{example}

\begin{example}\rm   $I'(C_{4})=3$ and $I''(C_{4})=4$; $I'(C_{5})=3$ and
$I''(C_{5})=4$; $I'(C_{6})=I''(C_{6})=3$; $I'(C_{7})=I''(C_{7})=4$;
$I'(C_{9})=I''(C_{9})=6$; $I'(C_{11})=I''(C_{11})=6$.

For $C_{4}$, $\{0,1,2\}$ is an identifying code, but
$\{0,1,2\}\subseteq B_{C_{4}}(1)$. For $C_{5}$, $\{0,1,2\}$ is
an identifying code, but $\{0,1,2\}\subseteq B_{C_{5}}(1)$ and $\{0,1,3\}$ can not separate $0$ and $1$.
For $C_{6}$, both $\{3,4,5\}$ and $\{0,2,4\}$ separate any pair of
distinct vertices. For $C_{7}$, $\{3,4,5,6\}$ separates any pair of
distinct vertices. For $C_{9}$,  both $\{3,4,5,6,7,8\}$ and
$\{0,2,4,6,7,8\}$ separate  any pair of distinct vertices. For
$C_{11}$, $\{3,4,5,8,9,10\}$ separates any pair of distinct
vertices.
\end{example}






The minimum cardinality of identifying codes of a path or a cycle
was computed in \cite{Be, Gr}.

\begin{prop}\label{pc} {\rm (\cite{Be, Gr})} {\rm(i)} For $n\geq3$,
$I(P_{n})=\lfloor\frac{n}{2}\rfloor+1$;

{\rm(ii)} For $n\geq 6$, $I(C_{n})=\left\{
\begin{array}{ll}
\frac{n}{2}, &n ~\textup{is even},\\
\frac{n+3}{2}, &n ~\textup{is odd}.
\end{array}\right.$
\end{prop}

In order to  compute the two parameters  for  paths  and cycle,
 we need the following useful lemma.



\begin{lemma}\label{rk'}
Let $H$ be an identifiable graph.

{\rm (i)} $I(H)-1\leq I'(H)\leq I(H)$;

{\rm (ii)} If $\Delta(H)\leq|V(H)|-2$, then $I(H)-1\leq I'(H)\leq I''(H)\leq
I(H)+1$, where $\Delta(H)$ is the maximum degree of   $H$.
\end{lemma}

\proof Let $C'$ be a code which separates any pair of distinct
vertices of $H$.

(i) Since there exists at most one vertex $v$ not covered by $C'$,
  $C'\cup \{v\}$  is an identifying code of $H$.
  Then $I(H)\leq I'(H)+1$, as desired.

(ii) Note that there exists at most one vertex $v$ such that
$C'\subseteq B_H(v)$. Since $\Delta(H)\leq|V(H)|-2$, there exists
$v_{0}\in V(H)\backslash B_H(v)$ such that $C''=C'\cup\{v_{0}\}$  is
a code which separates any pair of distinct vertices of $H$ and
satisfies $C''\not\subseteq B_{H}(w)$ for every $w\in V(H)$. It
follows that $I'(H)\leq I''(H)\leq I'(H)+1$. By (i), (ii) holds.
$\qed$



\begin{prop}\label{p}
For $n\geq 7$, $I'(P_{n})=I''(P_{n})=\lfloor\frac{n}{2}\rfloor+1$.
\end{prop}

\proof Combining Proposition~\ref{pc} and Lemma~\ref{rk'}, we have
$I'(P_{n})=\lfloor\frac{n}{2}\rfloor+1$ or
$\lfloor\frac{n}{2}\rfloor$. Suppose
$I'(P_{n})=\lfloor\frac{n}{2}\rfloor$. Then there exists a code $W'$
of size $\lfloor\frac{n}{2}\rfloor$ such that $W'$ separates any
pair of distinct vertices of $P_{n}$ and $B_{P_{n}}(i)\cap
W'=\emptyset$ for a unique vertex $i$.



\emph{Case 1}. $i\neq 0$ and $i\neq n-1$. Then $i-1,i,i+1\not\in
W'$, and $i-2,i-3,i-4,i+2,i+3,i+4\in W'$, so $4\leq i\leq n-5$. If
we delete the six vertices $i-1,i,i+1,i+2,i+3,i+4$, and connect
$i-2$ by an edge to $i+5$, then we get an identifying code of
$P_{n-6}$. Hence $|W'|\geq
3+I(P_{n-6})=\lfloor\frac{n}{2}\rfloor+1$,
 a contradiction.


\emph{Case 2}. $i=0$ or $n-1$. Without loss of generality, assume
that $i=n-1$. Then $n-1,n-2\not\in W'$, and $n-3,n-4,n-5\in W'$. If
$\{0,1,\ldots, n-6\}\subseteq W'$, then $|W'|=
n-2\geq\lfloor\frac{n}{2}\rfloor+1$, a contradiction. Now suppose
$\{0,1,\ldots, n-6\}\nsubseteq W'$. Take the smallest $k\geq 6$ such
that $n-k\not\in W'$. If $k=n-1$ or $k=n$, then $|W'|\geq
n-3\geq\lfloor\frac{n}{2}\rfloor+1$, a contradiction. It is clear
that $k\neq n-2$. For $k\leq n-3$, by deleting the vertices
$n-k,n-k+1,\ldots,n-1$, we get an identifying code of $P_{n-k}$. It
follows  that $|W'|\geq
k-3+I(P_{n-k})\geq\lfloor\frac{n}{2}\rfloor+1$, a contradiction.



Therefore, $I'(P_{n})=\lfloor\frac{n}{2}\rfloor+1$. Since
$I''(P_{n})=I'(P_{n})$ for $I'(P_{n})\geq 4$, the desired result
follows. $\qed$



\begin{prop}\label{c}
$I'(C_{n})=I''(C_{n})=\left\{
\begin{array}{ll}
\frac{n}{2}, &n \textup{ is even and }n\geq 8,\\
\frac{n+3}{2}, &n \textup{ is odd and }n\geq 13.
\end{array}\right.$
\end{prop}

\proof Note that $I''(C_{n})=I'(C_{n})$ for $I'(C_{n})\geq 4$.
Combining Proposition~\ref{pc} and Lemma~\ref{rk'}, we only need to prove
$I'(C_n)\geq I(C_n)$. It is routine to show that $I'(C_n)\geq
I(C_n)$ for $n=8$ or $n=10$. Next, we consider $n\geq 12$. Let $W'$
be a code of size $I'(C_n)$ such that $W'$ separates any pair of
distinct vertices of $C_{n}$. If $W'$ is an identifying code, then
$I'(C_n)=|W'|\geq I(C_n)$. Now suppose that $W'$ is not an
identifying code. Then there exists a unique vertex $i\in V(C_n)$
such that $\{i-1,i,i+1\}\cap W'=\emptyset$, which implies that
$\{i-2,i-3,i-4,i+2,i+3,i+4\}\subseteq W'$. If we delete the six
vertices $i-1,i,i+1,i+2,i+3,i+4$, and connect $i-2$ by an edge to
$i+5$, then we get an identifying code of $C_{n-6}$. Therefore
$I'(C_n)=|W'|\geq 3+I(C_{n-6})=I(C_n)$, as desired. $\qed$









\section{Main results}

We always assume that $G$ is a connected graph and $H$ is an
arbitrary graph. In this section, we first provide the sufficient
and necessary condition for $G[H]$ to be identifiable. Moreover, if
$G[H]$ is identifiable,  we determine the minimum cardinality of
identifying codes of $G[H]$ in terms of the order of $G$ and the two
parameters of $H$ given in Section 2.

The \emph{lexicographic product} $G[H]$ of graphs $G$ and $H$  is
the graph with the vertex set $\{(u,v)|u\in V(G),v\in V(H)\}$, and
the edge set $\{\{(u_1,v_1),(u_2,v_2)\}| d_G(u_1,u_2) =1, \textup{
or } u_1=u_2\textup{ and }d_H(v_1,v_2)=1\}$.
 For any two distinct vertices $(u_{1},v_{1})$, $(u_{2},v_{2})$ of $G[H]$, we observe that
\begin{equation}\label{distance}
d_{G[H]}((u_{1},v_{1}),(u_{2},v_{2}))=\left\{
\begin{array}{ll}
1,                 &\textup{if}~u_{1}=u_{2},d_{H}(v_{1},v_{2})=1,\\
2,                 &\textup{if}~u_{1}=u_{2},d_{H}(v_{1},v_{2})\geq2,\\
d_{G}(u_{1},u_{2}),&\textup{if}~u_{1}\neq u_{2}.
\end{array}\right.
\end{equation}

For $u\in V(G)$, let $N_{G}(u)=B_{G}(u)\backslash\{u\}$. For any
$u_{1},u_{2}\in V(G)$, define $u_{1}\equiv u_{2}$ if and only if
$B_{G}(u_{1})=B_{G}(u_{2})$ or $N_{G}(u_{1})=N_{G}(u_{2})$.
Hernando et al. \cite{He}  proved that $``\equiv"$ is an equivalent
relation and the equivalence class of a vertex is of three types: a
class of size $1$, a clique of size at least $2$, an independent set
of size at least $2$. Denote all equivalence classes by
\begin{equation}\label{class}
W_{1},\ldots,W_{p},U_{1},\ldots,U_{k},V_{1},\ldots,V_{l},
\end{equation}
where

(i) $|W_{q}|=1$, $q=1,\ldots,p$;

(ii) for any $u_{1},u_{2}\in U_{i},i=1,\ldots,k$,
$B_{G}(u_{1})=B_{G}(u_{2})$;

(iii) for any $u_{1},u_{2}\in V_{j},j=1,\ldots,l$,
$N_{G}(u_{1})=N_{G}(u_{2})$. \\* Denote
$s(G)=|U_{1}|+\cdots+|U_{k}|-k$, $t(G)=|V_{1}|+\cdots+|V_{l}|-l$.


For $u\in V(G)$ and $C\subseteq V(H)$, let $C^{u}=\{(u,v)|(u,v)\in V(G[H]), v\in C\}$.  For $S\subseteq V(G[H])$, let $S_{u}=\{v|v\in V(H), (u,v)\in S\}$. Note that $(S_u)^u=H^u\cap S$, where $H^{u}=(V(H))^{u}$.
 By (\ref{distance}), we have
\begin{equation}\label{equ}
B_{G[H]}((u,v))=(B_{H}(v))^{u}\cup\bigcup_{w\in N_{G}(u)} H^{w},
\end{equation}
\begin{equation}\label{equa}
B_{G[H]}((u,v))\cap S=((B_{H}(v))\cap S_u)^u\cup\bigcup_{w\in N_{G}(u)}(S_w)^w.
\end{equation}






\begin{thm}\label{exi} Let $G$ be a connected graph and $H$ be an
arbitrary graph.    Then the lexicographic product $G[H]$ of  $G$
and $H$ is identifiable if and only if

{\rm (i)}  $H$ is identifiable and $\Delta(H)\leq |V(H)|-2$; or

{\rm (ii)} both $G$ and $H$ are identifiable.
\end{thm}

\proof Suppose $G[H]$ is identifiable.  If $H$ is not identifiable,
then there exist two distinct vertices $v_{1},v_{2}$ of $H$ with
$B_{H}(v_{1})=B_{H}(v_{2})$. By (\ref{equ}),
$B_{G[H]}((u,v_{1}))=B_{G[H]}((u,v_{2}))$ for $u\in V(G)$. This
contradicts the condition that $G[H]$ is identifiable.

If $\Delta(H)=|V(H)|-1$ and $G$ is not identifiable, then
there exist  $v\in V(H)$  and two distinct vertices $u_{1},u_{2}$ of $G$ such that
$$B_{H}(v)=V(H) \textup{ and }B_{G}(u_{1})=B_{G}(u_{2}).$$
By (\ref{equ}),  we have
$$
B_{G[H]}((u_{1},v))=H^{u_{1}}\cup\bigcup_{u\in N_{G}(u_{1})}
H^{u}=\bigcup_{u\in B_{G}(u_{1})} H^{u}=\bigcup_{u\in B_{G}(u_{2})}
H^{u}=B_{G[H]}((u_{2},v)),
$$
which contradicts the condition that $G[H]$ is identifiable.

Therefore, (i) or (ii) holds.

Conversely, suppose (i) or (ii) holds.  Assume that $G[H]$ is not
identifiable. Therefore, there exist two distinct  vertices
$(u_{1},v_{1})$ and $(u_{2},v_{2})$  such that
$B_{G[H]}((u_{1},v_{1}))=B_{G[H]}((u_{2},v_{2}))$. If $u_{1}\neq
u_{2}$, then $d_G(u_1,u_2)=1$. It follows that
$B_{G}(u_{1})=B_{G}(u_{2})$ and $B_{H}(v_{1})=B_{H}(v_{2})=V(H)$,
contrary to (i) and (ii). If $u_{1}=u_{2}$, by (\ref{equ}), one gets
$B_{H}(v_{1})=B_{H}(v_{2})$, contrary to the condition that $H$ is
identifiable. $\qed$

\begin{re}
Let $r$ be a positive integer and $\Gamma$ be a graph. Given a vertex $v\in V(\Gamma)$, define $B_{\Gamma}^{(r)}(v)=\{u|u\in V(\Gamma),d_\Gamma(u,v)\leq r\}$. An $r$-\emph{identifying code} of $\Gamma$ is a code which $r$-covers all the vertices of $\Gamma$ and $r$-separates any pair of distinct vertices of $\Gamma$ (see \cite{Ka1} for details). Identifying codes in this paper are $1$-identifying codes. If $r\geq 2$, then $G[H]$ does not admit any $r$-identifying code. Indeed, by (\ref{distance}), $B_{G[H]}^{(r)}((u,v_1))=B_{G[H]}^{(r)}((u,v_2))$ for $r\geq 2$.
\end{re}



\begin{lemma}\label{geq} Let $G$ be a connected graph and $H$ be an
arbitrary graph.
 If $S$ is an identifying code of $G[H]$, then for any vertex $u$ of
$G$, $S_{u}$ separates any pair of distinct vertices of $H$.
Moreover, with reference to (\ref{class}), the following hold.

{\rm (i)} If $k\neq 0$, then there exists at most one vertex $u\in
U_{i}$ satisfying   $S_{u}\subseteq B_{H}(v)$ for a vertex $v$ of
$H$, where $i=1,\ldots,k$;

{\rm (ii)} If $l\neq 0$, then there exists at most one vertex $u\in
V_{j}$ satisfying   $S_{u}\cap B_{H}(v)=\emptyset$ for a vertex $v$
of $H$, where $j=1,\ldots,l$.
\end{lemma}

\proof  Assume that there exist $u_{0}\in V(G)$ and two distinct vertices $v_{1},v_{2}$ of $H$ such that $S_{u_{0}}\cap B_{H}(v_{1})=S_{u_{0}}\cap B_{H}(v_{2})$.
By (\ref{equa}), $B_{G[H]}((u_{0},v_{1}))\cap S=B_{G[H]}((u_{0},v_{2}))\cap S$,
contrary to the condition that $S$ is an identifying code of $G[H]$.

(i) Assume that there exist two distinct vertices $u_{1},u_{2}\in
U_{i}$ such that $S_{u_{1}}\subseteq B_{H}(v_{1})$ and
$S_{u_{2}}\subseteq B_{H}(v_{2})$. Since
$B_{G}(u_{1})=B_{G}(u_{2})$, by (\ref{equa})  we have
\begin{equation*}
B_{G[H]}((u_{1},v_{1}))\cap S=(S_{u_{1}})^{u_{1}}\cup\bigcup_{u\in N_{G}(u_{1})}(S_u)^u
                             =\bigcup_{u\in B_{G}(u_{2})}(S_u)^u
                             =B_{G[H]}((u_{2},v_{2}))\cap S.
\end{equation*}
Since $S$ is an identifying code of $G[H]$, we have
$(u_{1},v_{1})=(u_{2},v_{2})$, a contradiction.

(ii) Assume that there exist two different vertices $u_{1},u_{2}\in
V_{j}$ such that $S_{u_{1}}\cap B_{H}(v_{1})=S_{u_{2}}\cap
B_{H}(v_{2})=\emptyset$. Since $N_{G}(u_{1})=N_{G}(u_{2})$, by
(\ref{equa})  we have
\begin{equation*}
B_{G[H]}((u_{1},v_{1}))\cap S=\bigcup_{u\in N_{G}(u_{1})}(S_u)^u=\bigcup_{u\in N_{G}(u_{2})}(S_u)^u
                            =B_{G[H]}((u_{2},v_{2}))\cap S.
\end{equation*}
Since $S$ is an identifying code of $G[H]$, we obtain
$(u_{1},v_{1})=(u_{2},v_{2})$, a contradiction. $\qed$


In equivalence classes (\ref{class}) of $V(G)$,
choose $\overline{u}_{i}\in U_{i},i=1,\ldots,k$,
and $\overline{v}_{j}\in V_{j},j=1,\ldots,l$.
Let
$\overline{W}_{0}=\cup_{q=1}^{p}W_{q}\cup\{\overline{u}_{1},\ldots,\overline{u}_{k},\overline{v}_{1},\ldots,\overline{v}_{l}\}$
and
$\overline{U}_{i}=U_{i}\backslash\{\overline{u}_{i}\},i=1,\ldots,k$, $\overline{V}_{j}=V_{j}\backslash\{\overline{v}_{j}\},j=1,\ldots,l$. Therefore, we have a partition of $V(G)$:
\begin{equation}\label{partition}
\overline{W}_{0},\overline{U}_{1},\ldots,\overline{U}_{k},\overline{V}_{1},\ldots,\overline{V}_{l}.
\end{equation}

\begin{lemma}\label{leq}
Let $C$ be an identifying code of graph $H$, and let $C',C''$ be two
codes which separate any pair of distinct vertices of $H$ and
$C''\not\subseteq B_{H}(v)$ for every vertex $v$ of $H$. With
reference to (\ref{partition}),
\begin{equation*}
S=\bigcup_{u\in\overline{W}_{0}}(C')^{u}\cup\bigcup_{i=1}^{k}\bigcup_{u\in\overline{U}_{i}}(C'')^{u}\cup\bigcup_{i=1}^{l}\bigcup_{u\in\overline{V}_{i}}C^{u}
\end{equation*}
is an identifying code of $G[H]$.
\end{lemma}

\proof For any $u\in V(G)$, we have
\begin{equation*}
S_{u}=\left\{
\begin{array}{ll}
C', &\textup{ if }u\in \overline{W}_{0},\\
C'', &\textup{ if }u\in \cup_{i=1}^{k}\overline{U}_{i},\\
C,&\textup{ if }u\in \cup_{j=1}^{l}\overline{V}_{j}.
\end{array}\right.
\end{equation*}
Since $G$ is connected, there exists a vertex $w$ adjacent to $u$.
By (\ref{distance}), $S$ covers all vertices of $G[H]$. Hence, we
only need to show that, for any two distinct vertices
$(u_{1},v_{1})$ and $(u_{2},v_{2})$ of $G[H]$,
\begin{equation}\label{inequ}
B_{G[H]}((u_{1},v_{1}))\cap S\neq B_{G[H]}((u_{2},v_{2}))\cap S.
\end{equation}
If $u_{1}=u_{2}$, the fact that $S_{u_1}$ separates $v_1$ and $v_2$
implies $B_{H}(v_{1})\cap S_{u_1}\neq B_{H}(v_{2})\cap
S_{u_1}=B_{H}(v_{2})\cap S_{u_2}$, so  (\ref{inequ}) holds by
(\ref{equa}). Now suppose that $u_1\neq u_2$. In order to prove
(\ref{inequ}), it is sufficient to show that there exists
$(u_{0},v_{0})\in S$ such that
\begin{equation}\label{in1}
d_{G[H]}((u_{0},v_{0}),(u_{1},v_{1}))\leq 1,~d_{G[H]}((u_{0},v_{0}),(u_{2},v_{2}))\geq 2
\end{equation}
or
\begin{equation}\label{in2}
d_{G[H]}((u_{0},v_{0}),(u_{2},v_{2}))\leq 1,~d_{G[H]}((u_{0},v_{0}),(u_{1},v_{1}))\geq 2.
\end{equation}

\emph{Case 1}. $u_{1}\not\equiv u_{2}$. Then there exists $u_{0}\in
V(G)\backslash\{u_{1},u_{2}\}$ such that $d_{G}(u_{1},u_{0})=1$ and
$d_{G}(u_{2},u_{0})\geq 2$,  or $d_{G}(u_{1},u_{0})\geq 2$ and
$d_{G}(u_{2},u_{0})=1$. Take $v_0\in S_{u_0}$. Then
$(u_{0},v_{0})\in S$. By (\ref{distance}), (\ref{in1}) or
(\ref{in2}) holds.

\emph{Case 2}. $B_{G}(u_{1})=B_{G}(u_{2})$. Then $u_{1}$ and $u_{2}$
are adjacent and fall into some $U_i$. It follows that $u_1\in
\overline{U}_i$ or $u_2\in \overline{U}_i$. Without loss of
generality, suppose  $u_{1}\in \overline{U}_i$. Pick $u_{0}=u_{1}$.
Since $C''\not\subseteq B_{H}(v_{1})$, there exists $v_{0}\in C''$
such that $(u_{0},v_{0})\in S$ and $d_{H}(v_{0},v_{1})\geq 2$.  Then
(\ref{in2}) holds by (\ref{distance}).

\emph{Case 3}. $N_{G}(u_{1})=N_{G}(u_{2})$. Then $u_{1}$ and $u_{2}$
are at distance $2$ and fall into some $V_j$. It follows that
$u_1\in \overline{V}_j$ or $u_2\in \overline{V}_j$. Without loss of
generality, suppose  $u_{1}\in \overline{V}_j$. Pick $u_{0}=u_{1}$.
Since $C$ covers $v_{1}$, there exists $v_{0}\in C$ such that
$(u_{0},v_{0})\in S$ and $d_{H}(v_{0},v_{1})\leq 1$. By
(\ref{distance}), (\ref{in1}) holds. $\qed$


\begin{thm}\label{main}  Let $G$ be a connected graph and $H$ be an
arbitrary graph.   Suppose {\rm (i)} or {\rm (ii)} holds in Theorem
\ref{exi}.

{\rm (i)} If $\Delta(H)\leq|V(H)|-2$, then
\begin{equation}\label{equ2}
I(G[H])=(|V(G)|-s(G)-t(G))I'(H)+s(G)I''(H)+t(G)I(H);
\end{equation}

{\rm (ii)} If $\Delta(H)=|V(H)|-1$, then
\begin{equation}\label{equ1}
I(G[H])=(|V(G)|-t(G))I'(H)+t(G)I(H).
\end{equation}
\end{thm}

\proof
 (i) By Theorem \ref{exi}, $I(H)$ and $I'(H)$ are well defined. Since
$V(H)$ separates any pair of distinct vertices of $H$ and
$V(H)\not\subseteq B_{H}(v)$ for every $v\in V(H)$, $I''(H)$ is well
defined. Let $S$ be an identifying code of $G[H]$ with the minimum
cardinality, by Lemma \ref{geq},
\begin{equation*}
\begin{array}{lll}
I(G[H])&=&|S|=\sum\limits_{i=1}^{p}\sum\limits_{u\in W_{i}}|S_{u}|+\sum\limits_{i=1}^{k}\sum\limits_{u\in U_{i}}|S_{u}|+
\sum\limits_{i=1}^{l}\sum\limits_{u\in V_{i}}|S_{u}|\\
&\geq&(p+k+l)I'(H)+(\sum\limits_{i=1}^{k}|U_{i}|-k)I''(H)+(\sum\limits_{i=1}^{l}|V_{i}|-l)I(H)\\
&=&(|V(G)|-s(G)-t(G))I'(H)+s(G)I''(H)+t(G)I(H).
\end{array}
\end{equation*}
By Lemma~\ref{leq} we can construct an identifying code of $G[H]$
with cardinality $ (|V(G)|-s(G)-t(G))I'(H)+s(G)I''(H)+t(G)I(H)$.
Therefore, (\ref{equ2}) holds.

(ii) By Theorem \ref{exi}, both $G$ and $H$ are identifiable.
So $I(H)$ and $I'(H)$ are well defined.
Owing to $B_{G}(u_{1})\neq B_{G}(u_{2})$ for any two distinct vertices $u_{1},u_{2}$ of $G$,
we get $k=0$ in (\ref{class}) and (\ref{partition}).
Similar to the proof of (i), (\ref{equ1}) holds. $\qed$

Combining   Propositions \ref{pc}, \ref{p}, \ref{c} and Theorem
\ref{main}, we have the following results.

\begin{cor}
Let $G$ be a connected graph of order $m$ $(m\geq 2)$.

$(\textup{i})$ For $n\geq 7$,
$I(G[P_{n}])=m(\lfloor\frac{n}{2}\rfloor+1)$;

$(\textup{ii})$ For $n\geq 12$, $I(G[C_{n}])=\left\{
\begin{array}{ll}
\frac{mn}{2}, &n ~\textup{is even},\\
\frac{m(n+3)}{2}, &n ~\textup{is odd}.
\end{array}\right.$
\end{cor}


\paragraph{Acknowledgement: }
The authors are indebted to the anonymous reviewer for providing 
 simple proofs of Propositions~\ref{p} and \ref{c}. This
research is supported by NSFC(11271047), SRFDP and the Fundamental
Research Funds for the Central University of China.

\SquashBibFurther
\begin{thebibliography}{99}

\bibitem{ben} Y. Ben-Haim, S. Litsyn,
Exact minimum density of codes identifying vertices in the square
grid, {\em SIAM J. Discrete Math.} {\bf 19} (2005) 69--82.



\bibitem{Be} N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and
locating-dominating codes on chains and cycles, {\em European J.
Combin.} {\bf 25} (2004) 969--987.

\bibitem{Bl1} U. Blass, I. Honkala, S. Litsyn, On binary codes for identification,
{\em J. Combin. Designs} {\bf 8} (2000) 151--156.

\bibitem{Ch} I. Charon, O. Hudry, A. Lobstein, Minimizing the cardinality of an identifying or
locating-dominating code in a graph is NP-hard, {\em Theoret. Comp.
Sci.} {\bf 290} (2003) 2109--2120.

\bibitem{Coh} G. Cohen, I. Honkala, A. Lobstein, G. Z\'emor, On identifying codes, in: A. Barg, S. Litsyn(Eds.),
Codes and Association Schemes, in: DIMACS Series, vol.56, American
Mathematical Society, Providence, RI  (2001)  97-109.

\bibitem{coh2} G. Cohen, S. Gravier, I. Honkala, A. Lobstein, M. Mollard, C.
Payan, G. Z\'emor, Improved identifying codes for the grid,
 {\em Electron. J. Combin.}   {\bf 6} (1999) R19 Comments.

\bibitem{Gr} S. Gravier, J. Moncel, A. Semri, Identifying codes of cycles,
{\em European J.   Combin.} {\bf 27} (2006) 767--776.

\bibitem{Gra} S. Gravier, J. Moncel, A. Semri, Identifying codes of Cartesian product of two cliques of the same size,
 {\em Electron. J. Combin.} {\bf 15} (2008)  N4.


\bibitem{He} C. Hernando, M. Mora, I. M. Pelayo, C. Seara and D. R. Wood, Extremal graph theory for metric dimension and diameter,
{\em Electronic J. Combin.} {\bf 17} (2010) R30.

%{\em Electron. Notes in Discrete Math.} {\bf 29} (2007) 339--343.

\bibitem{ho} I. Honkala, T. Laihonen, On identifying codes in the
triangular and square grids, {\em SIAM J. Comput.} {\bf 33} (2004)
304--312.

\bibitem{Ho}  I. Honkala, A. Lobstein, On identifying codes in binary Hamming
spaces, {\em  J. Combin. Theory Ser. A} {\bf 99} (2002) 232--243.

\bibitem{Ka1}  M.G. Karpovsky, K. Chakrabarty, L.B. Levitin, On a new class of codes for identifying vertices in
graphs, {\em IEEE Trans. Inform. Theory} {\bf  44} (1998) 599--611.

\bibitem{Ka2} M.G. Karpovsky, K. Chakrabarty, L.B. Levitin, D.R. Avresky, On the
covering of vertices for fault diagnosis in hypercubes, {\em Inform.
Process. Lett.} {\bf 69} (1999) 99--103.


\bibitem{Mo} J. Moncel, Monotonicity of the minimum cardinality of an identifying code in the hypercube,
{\em Discrete Appl. Math.} {\bf 154} (2006) 898--899.

\bibitem{r} D.F. Rall, K. Wash, Identifying codes of the direct product of two
cliques, arXiv:1206.3596v1 [math. CO], 2012.

\bibitem{Xu} M. Xu, K. Thulasiraman, X. Hu,
Identifying codes of cycles with odd orders, {\em European J.
Combin.} {\bf 29} (2008) 1717--1720.


\end{thebibliography}


\end{CJK*}
\end{document}
