Graphe local
- Graphe local
-
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 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
Voir aussi
Liens internes
Liens externes
Références
- ↑ Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.
- ↑ Doro, S. "Two New Distance-Transitive Graphs." Unpublished.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe local de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe local de McLaughlin — Représentation du graphe local de McLaughlin. Nombre de sommets 162 Nombre d arêtes 4 536 Distribution des degrés 56 régulier Rayon … Wikipédia en Français
Graphe de McLaughlin — Nombre de sommets 275 Nombre d arêtes 15 400 Distribution des degrés 112 régulier Rayon 2 Diamètre 2 Maille 3 Automorphismes 1 796 256 000 … Wikipédia en Français
Graphe fortement régulier — Le graphe de Paley d ordre 13, un graphe fortement régulier de type (13,6,2,3). En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe qui est en particulier un graphe régulier. Soit G =… … Wikipédia en Français
Hypercube (graphe) — Pour les articles homonymes, voir Hypercube (homonymie). Cette page se comprend mieux après la lecture de Théorie des graphes. Hypercube … Wikipédia en Français
Hypercube (Graphe) — Pour les articles homonymes, voir Hypercube (homonymie). Cette page se comprend mieux après la lecture de Théorie des graphes. Hypercube … Wikipédia en Français
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
SYSTÈMES DYNAMIQUES DIFFÉRENTIABLES — Sans doute née avec le mémoire que Poincaré écrivit en 1881 «sur les courbes définies par des équations différentielles», où l’étude quantitative (analytique) locale des équations différentielles dans le champ complexe est remplacée par leur… … Encyclopédie Universelle
Combinatoire probabiliste — Méthode probabiliste Cet article n est pas sur les systèmes de preuve interactive qui sont utilisés pour convaincre un vérificateur qu une démonstration est correcte, ni sur les algorithmes probabilistes, qui donnent la bonne réponse avec une… … Wikipédia en Français
Méthode probabiliste — Cet article n est pas sur les systèmes de preuve interactive qui sont utilisés pour convaincre un vérificateur qu une démonstration est correcte, ni sur les algorithmes probabilistes, qui donnent la bonne réponse avec une grande probabilité, mais … Wikipédia en Français
