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

https://hal.telecom-paristech.fr/hal-02286382
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 3:40:34 PM
Last modification on : Thursday, October 17, 2019 - 12:37:00 PM

Identifiers

  • HAL Id : hal-02286382, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7