Minimum Sizes of Identifying Codes in Graphs Differing by One Edge or One Vertex - Equipe Mathématiques discrètes, codage et cryptographie Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2012

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

Irène Charon
  • Fonction : Auteur
Olivier Hudry

Résumé

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.
Fichier principal
Vignette du fichier
CHHLforHAL.pdf (336.65 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00731811 , version 1 (13-09-2012)

Identifiants

  • HAL Id : hal-00731811 , version 1

Citer

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⟩
189 Consultations
78 Téléchargements

Partager

Gmail Facebook X LinkedIn More