Graphe de Conway-Smith

Graphe de Conway-Smith
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

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.

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é.

Sommaire

Propriétés

Propriétés générales

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

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

Le polynôme caractéristique du graphe de Conway-Smith est : (x + 4)6(x + 2)30x14(x − 5)12(x − 10). 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

Liens internes

Liens externes

Références

  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).

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Graphe de Kneser — Le graphe de Kneser KG5,2, isomorphe au graphe de Petersen Notation KGn,k Nombre de sommets Distribution des degrés …   Wikipédia en Français

  • Graphe de Hall — Nombre de sommets 65 Nombre d arêtes 325 Distribution des degrés 10 régulier Propriétés Distance transitif …   Wikipédia en Français

  • Graphe local — En théorie des graphes, un graphe G est dit être localement X si quel que soit le sommet s de G considéré, le sous graphe induit sur G par les voisins de s est isomorphe à X (si X est un graphe) ou à un graphe appartenant à X (si X est une… …   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

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Théorie des jeux — La théorie des jeux est un ensemble d outils pour analyser les situations dans lesquelles ce qu il est optimal de faire pour un agent (personne physique, entreprise, animal, ...) dépend des anticipations qu il forme sur ce que un ou plusieurs… …   Wikipédia en Français

  • Liste de fractales par dimension de Hausdorff — Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension topologique[1]. Sommaire 1… …   Wikipédia en Français

  • Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… …   Wikipédia en Français

  • Jeu à somme positive — Théorie des jeux Le dilemme du prisonnier est une célèbre illustration en théorie des jeux d un jeu à somme non nulle. La théorie des jeux constitue une approche mathématique de problèmes de stratégie tels qu’on en trouve en recherche… …   Wikipédia en Français

  • Theorie des jeux — Théorie des jeux Le dilemme du prisonnier est une célèbre illustration en théorie des jeux d un jeu à somme non nulle. La théorie des jeux constitue une approche mathématique de problèmes de stratégie tels qu’on en trouve en recherche… …   Wikipédia en Français

Share the article and excerpts

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