Graphe local

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
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.

Consultez la liste des tâches à accomplir en page de discussion.

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à été 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.