HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Minimum Sizes of Identifying Codes in Graphs Differing by One Edge or One Vertex

Abstract : Let $G$ be a simple, undirected graph with vertex set $V$. For $v \in V$ and $r \geq 1$, we denote by $B_{G,r}(v)$ the ball of radius $r$ and centre $v$. A set $C \subseteq V$ is said to be an $r$-identifying code in $G$ if the sets $B_{G,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, or by adding or deleting an edge. 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

Contributor : Antoine Lobstein Connect in order to contact the contributor
Submitted on : Thursday, September 13, 2012 - 4:09:15 PM
Last modification on : Monday, January 24, 2022 - 11:43:20 AM
Long-term archiving on: : Friday, December 14, 2012 - 3:57:44 AM


Files produced by the author(s)


  • HAL Id : hal-00731811, version 1


Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Minimum Sizes of Identifying Codes in Graphs Differing by One Edge or One Vertex. 2012. ⟨hal-00731811⟩



Record views


Files downloads