
arXiv: 1106.3607
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$.
Combinatorial codes, identifying code, Graph operations (line graphs, products, etc.), Applications of graph theory, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), lexicographic product of graphs
Combinatorial codes, identifying code, Graph operations (line graphs, products, etc.), Applications of graph theory, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), lexicographic product of graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
