Loading AI tools
De Wikipédia, l'encyclopédie libre
En théorie des graphes, un graphe non-orienté est semi-symétrique s'il est arête-transitif et régulier, mais pas sommet-transitif[1]. Autrement dit, un graphe est semi-symétrique s'il est régulier et si son groupe d'automorphismes agit transitivement sur ses arêtes, mais pas sur ses sommets.
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 |
Tout graphe semi-symétrique est biparti[2], et son groupe d'automorphisme agit transitivement sur les deux sous-ensembles de sommets de la bipartition[3].
Il n'existe aucun graphe semi-symétrique d'ordre 2p ou 2p2, où p est un nombre premier[4].
Le plus petit graphe semi-symétrique est le graphe de Folkman, qui possède 20 sommets[3].
Tous les graphes cubiques semi-symétriques d'ordre inférieur à 768 sont connus[5]. Le plus petit d'entre eux est le graphe de Gray, qui possède 54 sommets[6].
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.