Abstract FR:

En 1989, m. C. Heydemann, j. C. Meyer et d. Sotteau ont conjecture que, dans tout graphe sommet-transitif, il existe un routage de plus courtes chaines sommet-uniformes et ont demontre que leur conjecture etait vraie dans le cas particulier des graphes de cayley. Dans cette these on definit de nouvelles classes de graphes sommet-transitifs dans lesquels il existe un routage de plus courtes chaines sommet-uniforme: les graphes quasi-cayley, les graphes a k-orbites regulieres. On etudie les proprietes de ces nouvelles classes, en particulier les proprietes algebriques de leurs groupes d'automorphismes. Un corollaire de cette etude est que la conjecture est vraie pour les graphes sommet-transitifs de diametre 2. On donne des exemples de familles de graphes quasi-cayley qui ne sont pas des graphes de cayley, des exemples de familles de graphes a k-orbites regulieres qui ne sont pas des graphes quasi-cayley. A cette occasion, on etudie la couverture par des cycles sommet-disjoints de l'ensemble des sommets de certains odd-graphs et de certains graphes de johnson ce qui permet d'introduire de nouvelles matrices combinatoires: les tableaux bordelais. Le dernier chapitre est consacre a l'etude de l'arete-indice de transmission de certains graphes: line-graphs des graphes complets, graphes composes, graphes recursifs circulants, star-graphs