Graphe zéro-symé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 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].

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

  1. ↑ (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)
  2. ↑ (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 )