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
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

110

Files downloads

35