1-Identifying Codes on Trees
Australasian Journal of Combinatorics, Vol. 31, pp. 21-35, 2005.
Nathalie BERTRAND
ENS Cachan
61 avenue du Président Wilson
94235 Cachan cédex, France
bertrand@dptmaths.ens-cachan.fr
Irène CHARON, Olivier HUDRY & Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{charon, hudry, lobstein}@infres.enst.fr
Abstract. Consider a connected undirected graph G=(V,E), a subset C of vertices, and an integer r greater than or equal to 1; for any vertex v in V, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices within distance r from v.
If for all vertices v in V, the sets Br(v) $\cap$ C are all nonempty and different, then we call C an r-identifying code. We study the smallest cardinalities or densities of these codes in trees. In particular, we prove that, in a tree with n vertices, any 1-identifying code contains at least 3(n+1)/7 vertices, and, investigating the complete q-ary trees, we also prove that the minimum cardinality of a 1-identifying code in a complete binary tree with 2h -1 vertices is exactly $\lceil 20(2h -1)/31 \rceil$.