Identifying codes of lexicographic product of graphs (Q1953370)

Summary: 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 a 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\).