
Evènement pour le groupe GT Graphes et Applications
Date  20110429 14:0015:00 
Titre  Bounding the identifying code number of a graph using its degree parameters, a probabilistic approach 
Résumé  An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. Let M(G) denote the minimum size of an identifying code in G. It was conjectured recently that if G is connected, has n vertices and maximum degree d, M(G) <= nn/d+O(1).
In a first part, we use Lovász' Local Lemma to give new upper bounds on M(G) for various classes of graphs in order to get closer to the conjectured bound than already known results.
In a second part, we use the first moment method to give improved bounds for graphs having given minimum degree and girth 5. Moreover we show that these bounds are asymptotically tight by computing the identifying code number of random dregular graphs w.h.p. using the pairing model.
This is joint work with Guillem Perarnau (UPC, Barcelona). 
Lieu  Salle 178 
Orateur  Florent Foucaud 
Url  LaBRI 
Aucun document lié à cet événement. RetourRetour à l'index
 