Voir la source de Graphe semi-symétrique

{{Familles de graphes définies par leurs automorphismes}}
En [[théorie des graphes]], un [[graphe non-orienté]] est '''semi-symétrique''' s'il est [[Graphe arête-transitif|arête-transitif]] et [[Graphe régulier|régulier]], mais pas [[Graphe sommet-transitif|sommet-transitif]]<ref>{{Article|langue=en|prénom1=Dragan|nom1=Marušič|prénom2=Primož|nom2=Potočnik|titre=Semisymmetry of Generalized Folkman Graphs|périodique=European Journal of Combinatorics|volume=22|numéro=3|date=2001-03-01|issn=0195-6698|doi=10.1006/eujc.2000.0473|lire en ligne=http://www.sciencedirect.com/science/article/pii/S0195669800904736|consulté le=2019-07-03|pages=333–349}}</ref>. Autrement dit, un graphe est semi-symétrique s'il est régulier et si son [[Automorphisme de graphe|groupe d'automorphismes]] agit transitivement sur ses arêtes, mais pas sur ses sommets.

== Propriétés ==
Tout graphe semi-symétrique est [[Graphe biparti|biparti]]<ref name=":0">{{Ouvrage|langue=en|auteur1=Norman Biggs|titre=Algebraic Graph Theory, {{2nd}} Edition|éditeur=[[Cambridge University Press]]|année=1993|pages totales=214|passage=115-116|isbn=978-0-521-45897-9|lire en ligne=https://books.google.com/books?id=6TasRmIFOxQC&printsec=frontcover}}</ref>, et son groupe d'automorphisme agit transitivement sur les deux sous-ensembles de sommets de la bipartition<ref name=":1">{{Lien web|langue=en|nom1=Weisstein|prénom1=Eric W.|titre=Semisymmetric Graph|url=http://mathworld.wolfram.com/SemisymmetricGraph.html|site=mathworld.wolfram.com|consulté le=2019-07-03}}</ref>.

Il n'existe aucun graphe semi-symétrique d'ordre 2p ou 2p{{Exp|2}}, où p est un [[nombre premier]]<ref>{{Article|langue=en|prénom1=Jon|nom1=Folkman|titre=Regular line-symmetric graphs|périodique=Journal of Combinatorial Theory|volume=3|numéro=3|date=1967-10-01|issn=0021-9800|doi=10.1016/S0021-9800(67)80069-3|lire en ligne=http://www.sciencedirect.com/science/article/pii/S0021980067800693|consulté le=2019-07-03|pages=215–232}}</ref>.

== Exemples ==
Le plus petit graphe semi-symétrique est le [[graphe de Folkman]], qui possède 20 sommets<ref name=":1" />.

Tous les [[Graphe cubique|graphes cubiques]] semi-symétriques d'ordre inférieur à 768 sont connus<ref>{{Article|langue=en|prénom1=Marston|nom1=Conder|prénom2=Aleksander|nom2=Malnič|prénom3=Dragan|nom3=Marušič|prénom4=Primž|nom4=Potočnik|titre=A census of semisymmetric cubic graphs on up to 768 vertices|périodique=[[Journal of Algebraic Combinatorics]]|volume=23|numéro=3|date=2006-05-01|issn=1572-9192|doi=10.1007/s10801-006-7397-3|lire en ligne=https://doi.org/10.1007/s10801-006-7397-3|consulté le=2019-07-03|pages=255–294}}</ref>. Le plus petit d'entre eux est le [[graphe de Gray]], qui possède 54 sommets<ref>{{Article|langue=en|prénom1=Dragan|nom1=Marušič|prénom2=Tomaž|nom2=Pisanski|prénom3=Steve|nom3=Wilson|titre=The genus of the GRAY graph is 7|périodique=European Journal of Combinatorics|série=Topological Graph Theory and Graph Minors, second issue|volume=26|numéro=3|date=2005-04-01|issn=0195-6698|doi=10.1016/j.ejc.2004.01.015|lire en ligne=http://www.sciencedirect.com/science/article/pii/S0195669804000605|consulté le=2019-07-02|pages=377–385}}</ref>.

<gallery>
Fichier:Folkman graph alt.svg|[[Graphe de Folkman]], plus petit graphe semi-symétrique, à 20 sommets.
Fichier:Gray graph hamiltonian.svg|[[Graphe de Gray]], plus petit graphe cubique semi-symétrique, à 54 sommets.
Fichier:Ljubljana graph hamiltonian.svg|[[Graphe de Ljubljana]], graphe cubique semi-symétrique à 112 sommets.
Fichier:Tutte 12-cage.svg|[[12-cage de Tutte]], graphe cubique semi-symétrique à 126 sommets.
</gallery>

== Notes et références ==
{{Références}}

{{Portail|mathématiques}}

[[Catégorie:Famille de graphes]]