Théorème d'Hoffman-Singleton

Modèle:Sources Le théorème d'Hoffman-Singleton est un théorème de théorie des graphes, prouvé en 1960 par Alan Hoffman et Robert Singleton. Ce théorème établit que tout graphe de Moore de diamètre 2 ne peut avoir qu'un degré $d$ égal à 2, 3, 7 ou 57.

Exemples de graphes de Moore

• 
  Le pentagone est un graphe de Moore à 5 sommets ($d=2$).
• 
  Le graphe de Petersen est un graphe de Moore à 10 sommets ($d=3$).
• 
  Le graphe de Hoffman-Singleton est un graphe de Moore à 50 sommets Modèle:Nobr

L'existence d'un graphe de Moore de diamètre 2 de degré $d=57$ possédant 3250 sommets est encore un problème ouvert.

Voir aussi

Article connexe

Graphe régulier

Référence

Sujet ENS 1986 section A1 épreuve de MATH.2