On the Number of Optimal Identifying Codes in a Twin-Free Graph
Discrete Applied Mathematics, Vol. 180, pp. 111-119, 2015.
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
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 be a simple, undirected graph with vertex set V. For every 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 in G 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 or r-identifiable, and in this case, the smallest size of an r-identifying code in G is denoted by $\gamma$r(G).
We study the number of different optimal r-identifying codes C, i.e., such that |C|=\gamma$r(G), that a graph G can admit, and try to construct graphs having ''many'' such codes.