1-identifying codes on trees

Consider a connected undirected graph G = (V,E), a subset of vertices C ⊆ V, and an integer r ≥ 1; for any vertex v ∈ V, let B_r(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 ∈ V, the sets B_r(v) ∩ 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)/7vertices, 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 2^h - 1 vertices is exactly ⌈20(2^h - 1)/31⌉.