Minimum Sizes of Identifying Codes in Graphs Differing by One Vertex
Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, Vol. 5, pp. 119-136, 2013.
Irène CHARON (*), Iiro HONKALA (#), 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
{irene.charon, olivier.hudry, antoine.lobstein}@telecom-paristech.fr
(#) Department of Mathematics and Statistics
University of Turku, 20014 Turku, Finland
honkala@utu.fi
Résumé. Let G be a simple, undirected graph with vertex set V. For v in V and r an integer greater than or equal to 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 admitting an r-identifying code is called r-twin-free, and in this case the size of a smallest r-identifying code in G is denoted by $\gamma$r(G).
We study the following structural problem: let G be an r-twin-free graph, and G* be a graph obtained from G by adding or deleting a vertex. If G* is still r-twin-free, we compare the behaviours of $\gamma$r(G) and $\gamma$r(G*), establishing results on their possible differences and ratios.