Graphe zéro-symétrique
En théorie des graphes, un graphe zéro-symétrique est un graphe cubique tel que pour tout couple de sommets, il existe un unique automorphisme envoyant le premier sur le second[1]. On parle également de représentation graphique régulière cubique (GRR, pour Graphical Regular Representation) d'un groupe G lorsque le groupe des automorphismes du graphe zéro-symétrique est isomorphe à G[2].
| 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 | |
Propriétés
Le plus petit graphe zéro-symétrique, à 18 sommets et 27 arêtes.
Un graphe zéro-symétrique est sommet-transitif.
Le plus petit graphe zéro-symétrique possède 18 sommets et 27 arêtes ; il a pour notation LCF [-5,5]9.
Le cuboctaèdre tronqué et l'icosidodécaèdre tronqué sont des exemples de graphes zéro-symétriques planaires.
Notes et références
- (en) H. S. M. Coxeter, Roberto Frucht et David L. Powers, Zero-Symmetric Graphs: Trivalent Graphical Regular Representations of Groups, Academic Press, (ISBN 978-1-4832-6878-1, lire en ligne)
- (en) Lewis A. Nowitz et Mark E. Watkins, « Graphical Regular Representations of Non-Abelian Groups, I », Canadian Journal of Mathematics, vol. 24, no 6, , p. 993–1008 (ISSN 0008-414X et 1496-4279, DOI 10.4153/CJM-1972-101-5, lire en ligne, consulté le )
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.