Résumé : Un code identifiant d'un graphe est un sous-ensemble C de sommets qui est à la fois dominant (tout sommet du graphe a un voisin dans C ou appartient à C) et séparant (tous les sommets ont un voisinage distinct à l'intérieur de C). Dans cet exposé, nous faisons un tour d'horizon de quelques résultats sur cette notion. Nous proposons une caractérisation des graphes qui ont le code minimum de taille n-1, n étant l'ordre du graphe. Également nous nous intéressons à ce paramètre dans la classe des graphes adjoints. Si le temps le permet, nous parlerons de la complexité du problème dans différentes sous-classes des graphes parfaits.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr