Name
Abstract | ||
|---|---|---|
Consider a connected undirected graph G = (V, E), a subset of vertices C subset of V, and an integer r >= 1; for any vertex v is an element of 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 is an element of V, the sets B-r(v) boolean AND C are all nonempty and different, then we call Can 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(Pi+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 2(h) - 1 vertices is exactly [20(2(h) - 1)/3/1]. |
Year | Venue | DocType |
|---|---|---|
2005 | AUSTRALASIAN JOURNAL OF COMBINATORICS | Journal |
Volume | ISSN | Citations |
31 | 2202-3518 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathalie Bertrand | 1 | 250 | 17.84 |
| Irène Charon | 2 | 599 | 53.16 |
| Olivier Hudry | 3 | 659 | 64.10 |
| Antoine Lobstein | 4 | 718 | 89.14 |