2012/06/15 by Douglas F. Rall, Rall, Douglas F., Kirsti Wash +1
Computer Science · Engineering · #05C69 #05C76 #94B60 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1206.3596
openalex publication_date 2012/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. It was recently shown by Gravier, Moncel and Semri that the minimum cardinality of an identifying code for the Cartesian product of two cliques of the same order n is the floor of 3n/2. We consider identifying codes of the direct product of two cliques. In particular, we answer a question of Klavzar and determine the minimum cardinality of an identifying code for the direct product of any two cliques.