European Journal of Combinatorics, Vol. 25/7, pp. 969-987, 2004.

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 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 in V (respectively in V \ C), the sets B_r(v) $\cap$ C are all nonempty and different, then we call C an r-identifying code (respectively, an r-locating-dominating code). We study the smallest cardinalities or densities of these codes in chains (finite or infinite) and cycles.

Revenir à la page d'accueil