Résumé :
Soient un graphe non orienté connexe G = (X, A) et un entier r non nul.
Pour tout sommet x de G, on appelle boule de rayon r et de centre x et on
note B(x) l'ensemble des sommets reliés à x par une chaîne d'au plus r
arêtes de G. Soit C un sous-ensemble C de X. Pour tout élément x de X, on
note I(x) l'intersection de B(x) et de C. On dit que C est un code
r-identifiant de G si les ensembles I(x) sont tous non vides et deux à deux
différents quand x décrit X. S'il en existe, on s'intéresse à des codes
r-identifiants de cardinal minimum ; on note i(G) le cardinal minimum d'un
code r-identifiant de G.
Après avoir rappelé la condition simple portant sur G pour qu'il existe
un code r-identifiant dans G, on s'intéresse aux cardinaux possibles des
codes optimaux. Plus précisément, pour n fixé assez grand devant r, on
montre que l'encadrement suivant est applicable à pour tout graphe G
connexe à n sommets et tout entier r non nul : log(n + 1) <= i(G) <= n - 1
(ou log designe le logarithme en base 2). On montre enfin que les bornes
précédentes et toutes les valeurs intermédiaires sont atteintes par des
graphes appropriés.