Graphe de McLaughlin

Graphe de McLaughlin
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
Indice chromatique 113
Propriétés Régulier
Fortement régulier
Eulérien
Hamiltonien
Intégral
modifier Consultez la documentation du modèle

Le graphe de McLaughlin est, en théorie des graphes, un graphe 112-régulier possédant 275 sommets et 15400 arêtes.

Sommaire

Propriétés

Propriétés générales

Le diamètre du graphe de McLaughlin, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 112-sommet-connexe et d'un graphe 112-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 112 sommets ou de 112 arêtes.

Il est possible de construire à partir de ce graphe un autre graphe fortement régulier : le graphe local de McLaughlin. Pour cela, il suffit de supprimer un des sommets du graphe de McLaughlin ainsi que tout ses voisins.

Coloriage

L'indice chromatique du graphe de McLaughlin est 113. Il existe donc une 113-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.

Propriétés algébriques

Le groupe d'automorphismes du graphe de McLaughlin est d'ordre 1 796 256 000.

Le polynôme caractéristique du graphe de McLaughlin est : − (x − 112)(x − 2)252(x + 28)22. Ce polynôme caractéristique n'admet que des racines entières. Le graphe de McLaughlin est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

C'est également le seul graphe avec ce polynôme caractéristique : le graphe de McLaughlin est déterminé de façon unique par son spectre de graphe, l'ensemble des valeurs propres de sa matrice d'adjacence.

Voir aussi

Liens internes

Liens externes

Références



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe de McLaughlin 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 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 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

  • Groupes finis simples — Liste des groupes finis simples En mathématiques, la classification des groupes finis simples établit que chacun de ces groupes est soit un cyclique, soit alterné, soit membre d une des seize familles de groupes de type de Lie (incluant le groupe …   Wikipédia en Français

  • Liste Des Groupes Finis Simples — En mathématiques, la classification des groupes finis simples établit que chacun de ces groupes est soit un cyclique, soit alterné, soit membre d une des seize familles de groupes de type de Lie (incluant le groupe de Tits), soit l un des 26… …   Wikipédia en Français

  • Liste des groupes finis simples — En mathématiques, la classification des groupes finis simples établit que chacun de ces groupes est soit un cyclique, soit alterné, soit membre d une des seize familles de groupes de type de Lie (incluant le groupe de Tits), soit l un des 26… …   Wikipédia en Français

  • Graphem — Grapheme (auch: Grafeme, von griechisch γραφή graphē ‚Schrift‘ und Suffix em) sind die kleinsten bedeutungsunterscheidenden graphischen Einheiten des Schriftsystems einer bestimmten Sprache. Sie sind der sprachwissenschaftliche… …   Deutsch Wikipedia

Share the article and excerpts

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