Minimum Sizes of Identifying Codes in Graphs Differing by One Vertex
Résumé
Let G be a simple, undirected graph with vertex set V. For v belonging to V and
r >= 1, we denote by B_{G,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 intersections of sets B_{G,r}(v) and C, for v belonging to 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 dierences and ratios.