Graphe local

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 | modifier le code]

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à était découvert par Doro dans un article inédit[2]. C'est le graphe de Hall.

Autres exemples[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

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