The minimum identifying code graphs

Let GG be a graph and B(u)B(u) be the set of uu with all of its neighbors in GG. A set SS of vertices is called an identifying code of GG if, for every pair of distinct vertices uu and vv, both B(u)∩SB(u)∩S and B(v)∩SB(v)∩S are nonempty and distinct. A minimum identifying code of a graph GG is an identifying code of GG with minimum cardinality and M(G)M(G) is the cardinality of a minimum identifying code for GG. A minimum identifying code graph GG of order nn is a graph with M(G)=⌈log2(n+1)⌉M(G)=⌈log2(n+1)⌉ having the minimum number of edges. Moncel (2006) [5] constructed minimum identifying code graphs of order 2m−12m−1 for m≥2m≥2 and left the same problem but for arbitrary order open. In this paper, we aimed at the construction of connected minimum identifying code graphs in order to solve this problem for integer order greater than or equal to 4. Furthermore, we discussed some related properties.