Graphe asymétrique

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

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

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

  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