Graphe asymétrique

En théorie des graphes, un graphe asymétrique ou graphe identité est un graphe dont le groupe d'automorphismes est trivial. C'est donc un graphe n'admettant aucun automorphisme autre que l'identité.

Familles de graphes définies par leurs automorphismes
distance-transitif → distance-régulier ← fortement régulier
↓
symétrique (arc-transitif) ← t-transitif, (t ≥ 2) symétrique gauche (en)
↓
(si connexe)
sommet-transitif et arête-transitif		 → régulier et arête-transitif → arête-transitif
↓ ↓ ↓
sommet-transitif → régulier → (si biparti)
birégulier
↑
graphe de Cayley ← zéro-symétrique asymétrique
Les huit graphes asymétriques à 6 sommets

Le plus petit graphe asymétrique est le graphe singleton, qui est également un graphe symétrique. Si on exclut ce cas trivial, un graphe asymétrique doit avoir au moins 6 sommets[1]. Il existe 8 graphes asymétriques distincts à isomorphisme près à l'ordre 6, 152 à l'ordre 7, 3 696 à l'ordre 8, 135 004 à l'ordre 9, 7 971 848 à l'ordre 10 et 805 364 776 à l'ordre 11[2].

Parmi les graphes cubiques, le plus petit graphe asymétrique est le graphe de Frucht. Il a 12 sommets.

Sont également asymétriques le graphe de Kittell, le graphe 4-chromatique de Heawood et le graphe de Walther.

Références
  1. (en) Eric W. Weisstein, « Identity Graph », sur MathWorld
  2. (en) Number of asymmetric (not necessarily connected) graphs with n nodes : suite A003400 de l'OEIS
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.