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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...