Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe semi-symétrique
Résumé
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. 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.
Tout graphe semi-symétrique est biparti, et son groupe d'automorphisme agit transitivement sur les deux sous-ensembles de sommets de la bipartition.
Il n'existe aucun graphe semi-symétrique d'ordre 2p ou 2p, où p est un nombre premier.
Le plus petit graphe semi-symétrique est le graphe de Folkman, qui possède 20 sommets.
Tous les graphes cubiques semi-symétriques d'ordre inférieur à 768 sont connus. Le plus petit d'entre eux est le graphe de Gray, qui possède 54 sommets.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.