×

ID codes in Cartesian products of cliques. (English) Zbl 1274.05408

Summary: An identifying code in a graph \(G\) is a set \(D\) of vertices such that the closed neighborhood of each vertex of the graph has a nonempty, distinct intersection with \(D\). The minimum cardinality of an identifying code is denoted \(\gamma^{ID}(G)\). Building upon recent results of S. Gravier, J. Moncel and A. Semri [Electron. J. Comb. 15, No. 1, Research Paper N4, 7 p. (2008; Zbl 1180.05088)], we show for \(n\leq m\) that \(\gamma^{ID}(K_n\square K_m)= \max\{2m- n,m+\lfloor n/2\rfloor\}\).
Furthermore, we improve upon the bounds for \(\gamma^{ID}(G\square K_m)\) and explore the specific case when \(G\) is the Cartesian product of multiple cliques.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 1180.05088