Graphe de Hall
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
| Graphe de Hall | |
| Nombre de sommets | 65 |
|---|---|
| Nombre d'arêtes | 325 |
| Distribution des degrés | 10-régulier |
| Propriétés | Distance-transitif |
modifier  |
|
Le graphe de Hall est, en théorie des graphes, un graphe 10-régulier possédant 65 sommets et 325 arêtes. C'est localement un graphe de Petersen, c'est-à-dire que quel que soit le sommet s considéré, le sous-graphe induit par les 10 voisins de s est isomorphe au graphe de Petersen.
En 1980 Hall prouve qu'il existe exactement 3 graphes étant localement le graphe de Petersen[1]. Deux d'entre eux sont déjà connus : le graphe de Conway-Smith et le graphe de Kneser KG7,2. Le troisième n'avait jamais été publié (même s'il avait déjà été découvert par Doro dans un article inédit)[2].
Voir aussi[modifier | modifier le code]
Liens internes[modifier | modifier le code]
Liens externes[modifier | modifier le code]
- (en) Eric W. Weisstein, Hall Graph (MathWorld)
- (en) Eric W. Weisstein, Locally Petersen Graph (MathWorld)
Références[modifier | modifier le code]
- Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.
- Doro, S. "Two New Distance-Transitive Graphs." Unpublished.
