En théorie des graphes, un graphe G est dit être localement X si quel que soit le sommet s de G considéré, le sous-graphe induit sur G par les voisins de s est isomorphe à X (si X est un graphe) ou à un graphe appartenant à X (si X est une famille de graphe).
Graphe localement de Petersen Par exemple, dans un graphe localement de Petersen, 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 PetersenHall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.. 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éditDoro, S. "Two New Distance-Transitive Graphs." Unpublished.. C'est le graphe de Hall.
Autres exemples Le graphe de Gosset est localement le graphe de Schläfli. Le graphe de Klein est localement le graphe cycle . Pour tout n, le graphe complet est localement le graphe complet . Ainsi le graphe tétraédrique est localement le graphe triangle.
Voir aussi
Liens internes Théorie des graphes
Liens externes Eric W. Weisstein, Local Graph (MathWorld) Eric W. Weisstein, Locally Petersen Graph (MathWorld)
Références
Catégorie:Théorie des graphes