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$.
@article{10_37236_2974,
author = {Min Feng and Min Xu and Kaishun Wang},
title = {Identifying codes of lexicographic product of graphs},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {4},
doi = {10.37236/2974},
zbl = {1264.94119},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2974/}
}
TY - JOUR
AU - Min Feng
AU - Min Xu
AU - Kaishun Wang
TI - Identifying codes of lexicographic product of graphs
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/2974/
DO - 10.37236/2974
ID - 10_37236_2974
ER -
%0 Journal Article
%A Min Feng
%A Min Xu
%A Kaishun Wang
%T Identifying codes of lexicographic product of graphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2974/
%R 10.37236/2974
%F 10_37236_2974
Min Feng; Min Xu; Kaishun Wang. Identifying codes of lexicographic product of graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 4. doi: 10.37236/2974
