Jeudi 10 janvier 2008, à 14h30 en C047.
Orateur : David Auger (ENST).
Titre : Codes identifiants dans les graphes.
Transparents.

Soit G=(V,E) un graphe non-orienté et r un entier. Pour un sommet v, la boule de rayon r est l'ensemble B(v,r) des sommets qui peuvent être reliés à v par une chaîne comportant au plus r arêtes. Un code r-identifiant est une partie C de V telle que tous les ensembles B(x,r) \cap C soient non vides et distincts. Intuitivement, si l'on désigne un sommet quelconque v dans le graphe, le fait de savoir pour tout sommet c du code C si la distance d(c,v) est inférieure ou égale, ou supérieure à r, permet d'identifier v. Je présenterai plusieurs résultats portant sur la structure des graphes admettant des codes identifiants, dits graphes sans jumeaux, en particulier une preuve de la conjecture selon laquelle un graphe sans r-jumeaux admet en tant que sous-graphe (i.e. induit) une chaine comportant 2r+1 sommets. Je présenterai aussi quelques résultats de complexité, comme le fait que la recherche d'un code r-identifiant de cardinal minimum est un problème NP-difficile, même si l'on se restreint aux graphes planaires dont le degré maximal est au plus 3.