Graphe de Conway-Smith

Le graphe de Conway-Smith est, en théorie des graphes, un graphe 10-régulier possédant 63 sommets et 315 arêtes[1]. 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.

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
Hamiltonien
Sommet-transitif
Intégral

En 1980 Hall prouve qu'il existe exactement 3 graphes étant localement le graphe de Petersen[2]. Deux d'entre eux sont déjà connus : le graphe de Conway-Smith et le graphe de Kneser KG7,2. Le troisième, le graphe de Hall, n'avait jamais été publié.

Propriétés

modifier

Propriétés générales

modifier

Le diamètre du graphe de Conway-Smith, l'excentricité maximale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 3.

Propriétés algébriques

modifier

Le groupe d'automorphismes du graphe de Conway-Smith est un groupe d'ordre 15 120[3].

Le polynôme caractéristique de la matrice d'adjacence du graphe de Conway-Smith est :  . Il n'admet que des racines entières. Le graphe de Conway-Smith est donc un graphe intégral, un graphe dont le spectre est constitué d'entiers.

Voir aussi

modifier

Liens internes

modifier

Liens externes

modifier

Références

modifier
  1. (en) Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "The Conway-Smith Graph for 3-Sym(7)." §13.2B in Distance Regular Graphs. New York: Springer-Verlag, pp. 37, 224, and 399, 1989.
  2. (en) Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.
  3. (en) Leonard Soicher, Re: Graph of 3.Sym(7), construction du graphe sous GAP (www.gap-system.org).