Graphe d'Hoffman-Singleton
- Graphe d'Hoffman-Singleton
-
Graphe d'Hoffman-Singleton
| Graphe d'Hoffman-Singleton |
Schéma du graphe d'Hoffman-Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets.
|
| Nombre de sommets |
50 |
| Nombre d'arêtes |
175 |
| Distribution des degrés |
7-régulier |
| Diamètre |
2 |
| Propriétés |
Fortement régulier, intégral, symétrique, hamiltonien |
Le graphe d'Hoffman-Singleton est, en théorie des graphes, l'unique graphe régulier de degré 7, de diamètre 2 et de maille 5. Il possède 50 sommets et 175 arête[1]. Il doit son nom à Alan J. Hoffman et Robert R. Singleton qui le découvrirent en essayant de classifier les graphes de Moore[2].
Propriétés
Le groupe d'automorphisme du graphe d'Hoffman-Singleton est d'ordre 252 000 et agit transitivement sur les sommets, les arêtes et les arcs. Le graphe d'Hoffman-Singleton est donc un graphe symétrique[3].
Il est hamiltonien et a un nombre chromatique de 4[4]. Pour la coloration des arêtes il faut au moins 7 couleurs[5].
Le graphe d'Hoffman-Singleton est également :
- un graphe fortement régulier ;
- un graphe de Moore ;
- un graphe intégral ;
- la (7,5)-cage.
Références
- ↑ (en) Hoffman-Singleton Graph (Mathworld)
- ↑ « Moore graphs with diameter 2 and 3 », dans IBM Journal of Research and Development, vol. 5, no 4, 1960, p. 497–504 [texte intégral]
- ↑ (en) Hafner, P. R. "The Hoffman-Singleton Graph and Its Automorphisms." J. Algebraic Combin. 18, 7-12, 2003.
- ↑ (en) Brouwer, Andries E. Hoffman-Singleton graph
- ↑ (en) Royle, G. "Re: What is the Edge Chromatic Number of Hoffman-Singleton?" GRAPHNET@istserv.nodak.edu posting. Sept. 28, 2004. [1]
Catégorie : Graphe remarquable
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe d'Hoffman-Singleton de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe de Hoffman-Singleton — Schéma du graphe de Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés … Wikipédia en Français
Graphe D'Hoffman-Singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 … Wikipédia en Français
Graphe d'hoffman-singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 … Wikipédia en Français
Théorème d'Hoffman-Singleton — Le théorème d Hoffman Singleton établit en 1960 par Alan Hoffman (en) et Robert Singleton stipule que tout Graphe de Moore de diamètre 2 ne peut avoir qu un degré d égal à 2,3,7 ou 57. Sommaire 1 Les différents graphes de Moore … Wikipédia en Français
Graphe de Moore — En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F … 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 distance-régulier — En théorie des graphes, un graphe est distance régulier si pour tous sommets , le nombre de sommets voisins de u à distance i et le nombre de sommets voisins de v à distance j ne dépendent que de i,j et de la distance d(u,v) entre u et v.… … 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
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
