Evènement pour le groupe GT Graphes et Applications

Date 2011-04-29  14:00-15:00
TitreBounding 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) <= n-n/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 d-regular graphs w.h.p. using the pairing model. This is joint work with Guillem Perarnau (UPC, Barcelona).  
LieuSalle 178 
OrateurFlorent Foucaud 

Aucun document lié à cet événement.

Retour à l'index