Some results about a conjecture on identifying codes in complete suns
Olivier Hudry, Antoine C. Lobstein · International Transactions in Operational Research · 2016
Abstract Consider a graph and, for every vertex , denote by the set . A subset is an identifying code if the sets , , are nonempty and distinct. It is a locating–dominating code if the sets , , are nonempty and distinct. Let be the graph whose vertex set can be partitioned into two sets, and , where induces a clique and induces an independent set, with edges and , ; computations are carried modulo n. This graph is called a complete sun. We prove the conjecture that the smallest identifying code in has size equal to n. We also characterize and count all the identifying codes with size nin . Finally, we determine the sizes of the smallest LD codes in .