Skip to Main content Skip to Navigation
Reports

Taille minimum des codes identifiants dans les graphes différant par un sommet ou une arête

Résumé : Soit $G$ un graphe simple, non orienté, d'ensemble de sommets~$V$. Pour $v\in V$ et $r\geq 1$, on note $B_{G,r}(v)$ la boule de rayon~$r$ et centre~$v$. Un ensemble $\CC \subseteq V$ est appelé un {\it code} $r${\it -identifiant} dans~$G$ si les ensembles $B_{G,r}(v)\cap \CC$, $v\in V$, sont tous non vides et distincts. Un graphe $G$ admettant un code $r$-identifiant est dit {\it sans} $r${\it -jumeaux}, et dans ce cas la taille d'un plus petit code $r$-identifiant dans~$G$ est dénotée par~$\gamma_r(G)$. Nous étudions le probléme structurel suivant : soit $G$ un graphe sans $r$-jumeaux, et $G^*$ un graphe obtenu á partir de~$G$ en ajoutant ou en retirant un sommet, ou en ajoutant ou en retirant une arête. Si $G^*$ est encore sans $r$-jumeaux, nous comparons le comportement de $\gamma_r(G)$ et~$\gamma_r(G^*)$, et établissons des résultats sur leurs possibles différence et rapport.
Document type :
Reports
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00623981
Contributor : Olivier Hudry Connect in order to contact the contributor
Submitted on : Tuesday, September 20, 2011 - 4:09:17 PM
Last modification on : Monday, January 24, 2022 - 11:43:20 AM
Long-term archiving on: : Wednesday, December 21, 2011 - 2:21:00 AM

File

4.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00623981, version 1

Citation

Irene Charon, Olivier Hudry, Antoine Lobstein. Taille minimum des codes identifiants dans les graphes différant par un sommet ou une arête. 2011. ⟨hal-00623981⟩

Share

Metrics

Record views

115

Files downloads

37