Jeudi 12 mars 2009, à 14h30 en C048.
David Auger (TELECOM ParisTech).
Racines carrées de graphes.

Le carré d'un graphe non orienté G est le graphe G² construit sur le même ensemble de sommets en ajoutant à G les arêtes entre les sommets à distance 2 dans G (où la distance entre deux sommets s'entend au sens habituel du nombre d'arêtes de la plus courte chaîne qui les relie) ; autrement dit, deux sommets sont adjacents dans G² s'ils sont à distance 1 ou 2 dans G. Un graphe G est alors une racine carrée d'un graphe H (sur le même ensemble de sommets) si G²=H. Après un rappel de quelques résultats déjà connus autour de ces notions, on s'intéressera à la complexité algorithmique du problème de reconnaissance des carrés de graphes, ainsi que du calcul de la/des racine(s) carrée(s). Si la reconnaissance des carrés en toute généralité est un problème NP-difficile, il est en revanche possible de reconnaître en temps linéaire les carrés d'arbres, et dans le même temps de reconstituer, le cas échéant, leur unique racine carrée. Nous nous intéresserons à un problème intermédiaire, à savoir la reconnaissance des graphes qui sont carrés de graphes dont la maille vaut au moins 7, puis au moins 6. Nous montrerons qu'un graphe peut avoir au plus une racine carrée de maille supérieure à 7, mais peut admettre plusieurs racines carrées de maille 6 ; nous montrerons comment les calculer en temps polynomial, donnerons un majorant de leur nombre en fonction du nombre de sommets, et exhiberons des isomorphismes canoniques entre ces différentes racines.