Minimum Sizes of Identifying Codes in Graphs Differing by One Vertex - Télécom Paris Accéder directement au contenu
Article Dans Une Revue Cryptography and Communications - Discrete Structures, Boolean Functions and Sequences Année : 2013

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.
Fichier non déposé

Dates et versions

hal-02286382 , version 1 (13-09-2019)

Identifiants

  • HAL Id : hal-02286382 , version 1

Citer

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⟩
35 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More