Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 14 mai 2013 à 12h30 en B107, Petru Valicov nous parlera de : Quelques résultats sur les codes identifiants

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 : mercredi 20 mars 2013 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr