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é.
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
| 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 | |
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
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
