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

modifier

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 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]. C'est le graphe de Hall.

Autres exemples

modifier

Voir aussi

modifier

Liens internes

modifier

Liens externes

modifier

Références

modifier
  1. Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.
  2. Doro, S. "Two New Distance-Transitive Graphs." Unpublished.