Résumé de séminaire

Résumé :

Un graphe est dit k-connexe, respectivement k-arête-connexe, si pour toute paire de sommets il existe k chemins disjoints par les sommets, respectivement disjoints par les arêtes, joignant la paire de sommets. La distance séparant deux sommets du graphe est la longueur en nombre d'arêtes d'un plus court chemin joignant ces deux sommets. On dira qu'un graphe a un diamètre D si les deux sommets les plus éloignés du graphe sont à distance D.

Le problème auquel nous nous intéressons est de déterminer le nombre minimum d'arêtes que comporte un graphe contenant N sommets, 2-connexe ou 2-arête-connexe et dont le diamètre est D. Ce problème trouve notamment des applications dans le domaine des télécommunications car la 2-connexité permet de concevoir des réseaux résistant à une panne, et la 2-arête-connexité permet de résister à une panne de lien (en général plus probable). La notion de diamètre est étroitement liée à une notion de qualité de service: le délai maximum de communication entre deux utilisateurs qui croit avec le nombre de noeuds et d'arêtes à traverser.

Nous présenterons une preuve de la conjecture de B. Bollobas, selon laquelle le nombre minimum d'arêtes d'un graphe 2-connexe de diamètre D est (ND-2D-1)/(D-1). Nous démontrons aussi cette valeur pour les graphes 2-arête-connexes de diamètre D.

Références :

Home page : http://www-sop.inria.fr/mascotte/personnel/Aubin.Jarry/