Article ID Journal Published Year Pages File Type
4653599 European Journal of Combinatorics 2014 13 Pages PDF
Abstract

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. The minimum cardinality of an identifying code in a graph GG is denoted γID(G). It was recently shown by Gravier, Moncel and Semri that γID(Kn□Kn)=⌊3n2⌋. Letting n,m≥2n,m≥2 be any integers, we consider identifying codes of the direct product Kn×KmKn×Km. In particular, we answer a question of Klavžar and show the exact value of γID(Kn×Km).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,