Evènement pour le groupe GT Graphes et Applications

Date 2010-04-16  14:00-15:00
TitreExtremal cardinalities of identifying codes 
RésuméIdentifying codes are dominating sets with the property that any two vertices of the graph have distinct neighbourhoods within the identifying code. As a consequence, they can be used to uniquely identify or locate the vertices of a graph. Identifying codes have found many applications, such as for fault diagnosis in multiprocessor networks or the placement of emergency sensors in facilities, and have been widely studied since the introduction of the concept by Karpovski et al. in 1998. In this talk, we present some results on extremal cardinalities of identifying codes. The first part will consist of the characterization of the class of graphs on n vertices having very large minimum identifying codes (i.e. of size n or n-1). In a second part, we present some upper bounds on the minimum cardinality of an identifying code depending on parameters such as the minimum and maximum degree, or the girth of the graph.  
LieuSalle 178 
OrateurFlorent Foucaud 

Aucun document lié à cet événement.

Retour à l'index