\documentclass[12pt]{article} \usepackage{e-jc} \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\quad Min Xu\quad 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{June 26, 2011}{????}{????}\\ \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 {\em Key words:} identifying code; lexicographic product. %\medskip %\noindent {\em 2010 MSC:} 05C12, 05E30. \end{abstract} \bigskip \bigskip \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} \section*{Acknowledgement} The authors are indebted to the anonymous reviewer for providing the 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. \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) Comments to R19. \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 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}