On the Ensemble of Optimal Identifying Codes in a Twin-Free Graph
Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, Vol. 8, pp. 139-153, 2016.
Iiro HONKALA (#), Olivier HUDRY (*) & Antoine LOBSTEIN (*)
(#) Department of Mathematics and Statistics
University of Turku, 20014 Turku, Finland
honkala@utu.fi
(*) Centre National de la Recherche Scientifique
LTCI Laboratoire de Traitement et Communication de l'Information
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{olivier.hudry, antoine.lobstein}@telecom-paristech.fr
Résumé. Let G=(V,E) be a graph. For v in V and r>=1, we denote by BG,r(v) the ball of radius r and centre v. A subset C of V is said to be an r-identifying code if the sets BG,r(v) $\cap$ C, v in V, are all nonempty and distinct. A graph G which admits an r-identifying code is called r-twin-free, and in this case, the smallest size of an r-identifying code in G is denoted by $\gamma$r(G).
We study the ensemble of all the different optimal r-identifying codes C, i.e., such that |C|=$\gamma$r(G). We show that, given any collection A of k-subsets of V1={1,2,...,n}, there is a positive integer m, a graph G=(V,E) with V=V1 $\cup$ V2, where V2={n+1,...,n+m}, and a subset S of V2 such that C is an optimal r-identifying code in G if, and only if, C=a $\cup$ S for some a in A. This result gives a direct connection with induced subgraphs of Johnson graphs, which are graphs with vertex set a collection of k-subsets of V1, with edges between any two vertices sharing k-1 elements.