Graphe de Hall
- Graphe de Hall
-
| Graphe de Hall |
| Nombre de sommets |
65 |
| Nombre d'arêtes |
325 |
| Distribution des degrés |
10-régulier |
| Propriétés |
Distance-transitif |
modifier  |
Le graphe de Hall est, en théorie des graphes, un graphe 10-régulier possédant 65 sommets et 325 arêtes. C'est localement un graphe de Petersen, c'est-à-dire que 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].
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 de Hall de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe de Hall-Janko — Représentation du graphe de Hall Janko Nombre de sommets 100 Nombre d arêtes 1800 Distribution des degrés 36 régulier Rayon … Wikipédia en Français
Graphe de Kneser — Le graphe de Kneser KG5,2, isomorphe au graphe de Petersen Notation KGn,k Nombre de sommets Distribution des degrés … Wikipédia en Français
Graphe de Conway-Smith — Nombre de sommets 63 Nombre d arêtes 315 Distribution des degrés 10 régulier Diamètre 4 Maille 3 Automorphismes 15 120 Propriétés Distance transitif … Wikipédia en Français
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… … Wikipédia en Français
Graphe intégral — En théorie des graphes, un graphe intégral est un graphe dont le spectre de la matrice d adjacence ne contient que des entiers[1]. En d autres termes, les racines de son polynôme caractéristiques sont toutes entières. Leur étude fut introduite… … Wikipédia en Français
Graphe des liaisons — Graphe de liaisons Un Bond Graph également appelé Graphe à liens ou Graphe de liaisons est une représentation graphique d un système dynamique physique (mécanique, électrique, hydraulique, pneumatique, etc.) qui représente les transferts d… … Wikipédia en Français
Graphe à liens — Graphe de liaisons Un Bond Graph également appelé Graphe à liens ou Graphe de liaisons est une représentation graphique d un système dynamique physique (mécanique, électrique, hydraulique, pneumatique, etc.) qui représente les transferts d… … Wikipédia en Français
Graphe de liaisons — Pour les articles homonymes, voir Graphe de liaisons (homonymie). Un graphe de liaisons également appelé graphe à liens ou bond graph est une représentation graphique d un système dynamique physique (mécanique, électrique, hydraulique,… … Wikipédia en Français
Théoreme de Hall — Théorème de Hall Le théorème de Hall donne une condition nécessaire et suffisante à l existence d un couplage parfait dans un graphe biparti (un couplage parfait dans un graphe ayant un nombre pair 2n de sommets est un sous ensemble de n arêtes… … Wikipédia en Français
Théorème de hall — Le théorème de Hall donne une condition nécessaire et suffisante à l existence d un couplage parfait dans un graphe biparti (un couplage parfait dans un graphe ayant un nombre pair 2n de sommets est un sous ensemble de n arêtes deux à deux… … Wikipédia en Français
