Independent identifying codes: complexity and closed formulas for some graph classes

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. An independent identifying code (an IIC set) is an identifying code that is also independent. This paper investigates the problem of determining an independent identifying code in a given nontrivial simple undirected connected graph. We prove that the problems of determining the existence of IIC sets in planar bipartite graphs and in graphs with maximum degree four are NP-complete. Furthermore, we study IIC sets in certain infinite families of snarks -- namely, flower snarks, generalized Blanuša snarks, and Goldberg snarks. For the first two families, we provide closed formulas for the size of an IIC set; for the third, we prove that no such code exists.