Skip to Main content Skip to Navigation
Journal articles

Minimum Sizes of Identifying Codes in Graphs Differing by One Vertex

Abstract : 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.
Complete list of metadatas
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 3:40:34 PM
Last modification on : Friday, July 31, 2020 - 11:28:04 AM


  • HAL Id : hal-02286382, version 1


Irène Charon, I. Honkala, Olivier Hudry, Antoine Lobstein. Minimum Sizes of Identifying Codes in Graphs Differing by One Vertex. Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences, 2013, 5, pp.119-136. ⟨hal-02286382⟩



Record views