Identifying Codes of Cartesian Product of Two Cliques of the Same Size

S. Gravier, J. Moncel, A. Semri


We determine the minimum cardinality of an identifying code of $K_n\square K_n$, the Cartesian product of two cliques of same size. Moreover we show that this code is unique, up to row and column permutations, when $n\geq 5$ is odd. If $n\geq 4$ is even, we exhibit two distinct optimal identifying codes.

Full Text: PDF