Graphe semi-symétrique
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 | |
Propriétés
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].
Exemples
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].
Graphe de Folkman, plus petit graphe semi-symétrique, à 20 sommets.
Graphe de Gray, plus petit graphe cubique semi-symétrique, à 54 sommets.
Graphe de Ljubljana, graphe cubique semi-symétrique à 112 sommets.
12-cage de Tutte, graphe cubique semi-symétrique à 126 sommets.
Notes et références
- (en) Dragan MaruĆĄiÄ et PrimoĆŸ PotoÄnik, « Semisymmetry of Generalized Folkman Graphs », European Journal of Combinatorics, vol. 22, no 3,â , p. 333â349 (ISSN 0195-6698, DOI 10.1006/eujc.2000.0473, lire en ligne, consultĂ© le )
- (en) Norman Biggs, Algebraic Graph Theory, 2d Edition, Cambridge University Press, , 214 p. (ISBN 978-0-521-45897-9, lire en ligne), p. 115-116
- (en) Eric W. Weisstein, « Semisymmetric Graph », sur mathworld.wolfram.com (consulté le )
- (en) Jon Folkman, « Regular line-symmetric graphs », Journal of Combinatorial Theory, vol. 3, no 3,â , p. 215â232 (ISSN 0021-9800, DOI 10.1016/S0021-9800(67)80069-3, lire en ligne, consultĂ© le )
- (en) Marston Conder, Aleksander MalniÄ, Dragan MaruĆĄiÄ et PrimĆŸ PotoÄnik, « A census of semisymmetric cubic graphs on up to 768 vertices », Journal of Algebraic Combinatorics, vol. 23, no 3,â , p. 255â294 (ISSN 1572-9192, DOI 10.1007/s10801-006-7397-3, lire en ligne, consultĂ© le )
- (en) Dragan MaruĆĄiÄ, TomaĆŸ Pisanski et Steve Wilson, « The genus of the GRAY graph is 7 », European Journal of Combinatorics, topological Graph Theory and Graph Minors, second issue, vol. 26, no 3,â , p. 377â385 (ISSN 0195-6698, DOI 10.1016/j.ejc.2004.01.015, lire en ligne, consultĂ© le )