Some Results About a Conjecture on Identifying Codes in Complete Suns
International Transactions in Operational Research, Vol. 26, pp. 732-746, 2019.
Olivier HUDRY (#) & Antoine LOBSTEIN (*)
(#) Département Informatique et Réseaux, LTCI,
Télécom ParisTech, Université Paris-Saclay,
46 rue Barrault, 75634 Paris Cedex 13 - France
olivier.hudry@telecom-paristech.fr
(*) Centre National de la Recherche Scientifique,
Laboratoire de Recherche en Informatique, UMR 8623,
Université Paris-Sud, Université Paris-Saclay,
Bâtiment 650 Ada Lovelace, 91405 Orsay Cedex - France
antoine.lobstein@lri.fr
Abstract. Consider a graph G=(V,E) and, for every vertex v in V, denote by B(v) the set {v} $\cup$ {u: uv in E}. A subset C of V is an identifying code if the sets B(v) $\cap$ C, v in V, are nonempty and distinct. It is a locating-dominating code if the sets B(v) $\cap$ C, v in V\C, are nonempty and distinct.
Let Sn be the graph whose vertex set can be partitioned into two sets Un and Vn, where Un={u1, u2, ..., un} induces a clique, and Vn={v1,2, v2,3, ..., vn-1,n, vn,1} induces an independent set, with edges vi,i+1ui and vi,i+1ui+1, 1 =< i =< n; computations are carried modulo n. This graph is called a complete sun. We prove the conjecture, stated by Argiroffo, Bianchi and Wagler in 2014, that the smallest identifying code in Sn has size equal to n. We also characterize and count all the identifying codes with size n in Sn. Finally, we determine the sizes of the smallest locating-dominating codes in Sn.