Graphe local de McLaughlin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Graphe local de McLaughlin
Image illustrative de l'article 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 2
Diamètre 2
Maille 3
Propriétés Eulérien
Hamiltonien
Fortement régulier
Intégral

Le graphe local de McLaughlin est, en théorie des graphes, un 56-régulier possédant 162 sommets et 4 536 arêtes. C'est plus précisément l'unique graphe fortement régulier de paramètres (162,56,10,24), unicité prouvée par Cameron, Goethals et Seidel en 1978[1]. Il peut être construit à partir du graphe de McLaughlin en supprimant un de ses sommets ainsi que tous ses voisins.

Propriétés[modifier | modifier le code]

Propriétés générales[modifier | modifier le code]

Le diamètre du graphe local 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 56-sommet-connexe et d'un graphe 56-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 56 sommets ou de 56 arêtes.

Propriétés algébriques[modifier | modifier le code]

Le polynôme caractéristique de la matrice d'adjacence du graphe local de McLaughlin est : (x-56) (x-2)^{140} (x+16)^{21}. Ce polynôme caractéristique n'admet que des racines entières. Le graphe local 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 local de McLaughlin est déterminé de façon unique par son spectre de graphe, l'ensemble des valeurs propres de sa matrice d'adjacence[2].

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. P.J. Cameron, J.-M. Goethals & J.J. Seidel, Strongly regular graphs having strongly regular subconstituents, J. Algebra 55 (1978) 257-280.
  2. van Dam, E. R. and Haemers, W. H. « Spectral Characterizations of Some Distance-Regular Graphs. » J. Algebraic Combin. 15, 189-202, 2003