Graphe de Hoffman-Singleton

Graphe de Hoffman-Singleton
Graphe de Hoffman-Singleton
Hoffman singleton graph circle2.gif
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 7-régulier
Rayon 2
Diamètre 2
Maille 5
Automorphismes 252 000
Nombre chromatique 4
Indice chromatique 7
Propriétés Cage
Fortement régulier
Graphe de Cayley
Graphe de Moore
Hamiltonien
Intégral
Symétrique

Le graphe de Hoffman-Singleton est, en théorie des graphes, un graphe possédant 50 sommets et 175 arêtes[1]. C'est Alan Hoffman (en) et Robert Singleton qui le découvrirent en essayant de classifier les graphes de Moore[2].

Sommaire

Construction

Il est possible de construire le graphe de Hoffman-Singleton à partir de pentagones et de pentagrammes. Considérons C5 le graphe cycle à cinq sommets, représenté comme une pentagone, et P5, le même graphe représenté comme une pentagramme. Prenons cinq copies de C5, notés C1 à C5 et cinq copies de P5 notés P1 à P5. Pour tout triplet (i, j,h), relions le sommet numéro j de Ch au sommet numéro hi+j modulo 5 de Pi. Le graphe obtenu a 5 × 5 + 5 × 5 = 50 sommets et 175 arêtes.

Le graphe de Hoffman-Singleton peut aussi être vu comme un sous-graphe du graphe de Higman-Sims.

Propriétés

Propriétés générales

Le graphe de Hoffman-Singleton est une (7,5)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 5 et étant un graphe régulier de degré 7. Il s'agit de l'unique (3,7)-cage et sa taille coïncide avec la borne de Moore, une borne inférieure sur le nombre de sommets que peut avoir une cage. Un tel graphe est qualifié de graphe de Moore.

Le diamètre du graphe de Hoffman-Singleton, l'excentricité maximale de ses sommets, ainsi que son rayon, l'excentricité minimale de ses sommets, sont tous deux égaux à 2. Cela entraine que tous ses sommets appartiennent à son centre.

Le graphe de Hoffman-Singleton est 7-sommet-connexe et 7-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 7 sommets ou de 7 arêtes. Comme il est régulier de degrés 7 ce nombre est optimal. Le graphe de Hoffman-Singleton est donc un graphe optimalement connecté.

Il est également hamiltonien, c'est-à-dire qu'il possède un cycle passant par tous les sommets une et une seule fois. .

Coloriage

Le nombre chromatique du graphe de Hoffman-Singleton est 4. C'est-à-dire qu'il est possible de le colorer avec 4 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes. Ce nombre est minimal[3].

L'indice chromatique du graphe de Hoffman-Singleton est 7. Il existe donc une 7-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal[4].

Propriétés algébriques

Le groupe d'automorphismes du graphe de Hoffman-Singleton est d'ordre 252 000. Il agit transitivement sur les sommets, les arêtes et les arcs. Le graphe d'Hoffman-Singleton est donc un graphe symétrique[5].

Le graphe de Hoffman-Singleton est également un graphe de Cayley.

Le polynôme caractéristique du graphe de Hoffman-Singleton est : (X - 7)(X - 2)28(X + 3)21. Ce polynôme caractéristique n'admet que des racines entières. Le graphe de Hoffman-Singleton est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers. C'est aussi le seul graphe avec ce polynôme caractéristique ce qui fait de lui un graphe déterminé de façon unique par son spectre, c'est-à-dire l'ensemble des valeurs propres de sa matrice d'adjacence.

Références

  1. (en) Eric W. Weisstein, « Hoffman-Singleton Graph », MathWorld
  2. (en) Alan J. Hoffman et Robert R. Singleton, « Moore graphs with diameter 2 and 3 », dans IBM Journal of Research and Development, vol. 5, no 4, novembre 1960, p. 497–504 [lien DOI] 
  3. (en) Hoffman-Singleton graph sur la page d'Andries E. Brouwer, de l'université technique d'Eindhoven
  4. (en) Re: What is the Edge Chromatic Number of Hoffman-Singleton?, réponse de Gordon Royle en 2004, sur le forum GRAPHNET@istserv.nodak.edu
  5. (en) Paul R. Hafner, « The Hoffman-Singleton Graph and Its Automorphisms », dans Journal of Algebraic Combinatorics (en), vol. 18, no 1, 2003, p. 7-12 [texte intégral (ps), lien DOI (pages consultées le 14 septembre 2010)] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de Hoffman-Singleton de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • 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

  • 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”