Ê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 GraphSearch.
Concept
Graphe sommet-transitif
Résumé
In the mathematical field of graph theory, a vertex-transitive graph is a graph G in which, given any two vertices v_1 and v_2 of G, there is some automorphism
such that
In other words, a graph is vertex-transitive if its automorphism group acts transitively on its vertices. A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical.
Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph).
Finite vertex-transitive graphs include the symmetric graphs (such as the Petersen graph, the Heawood graph and the vertices and edges of the Platonic solids). The finite Cayley graphs (such as cube-connected cycles) are also vertex-transitive, as are the vertices and edges of the Archimedean solids (though only two of these are symmetric). Potočnik, Spiga and Verret have constructed a census of all connected cubic vertex-transitive graphs on at most 1280 vertices.
Although every Cayley graph is vertex-transitive, there exist other vertex-transitive graphs that are not Cayley graphs. The most famous example is the Petersen graph, but others can be constructed including the line graphs of edge-transitive non-bipartite graphs with odd vertex degrees.
The edge-connectivity of a vertex-transitive graph is equal to the degree d, while the vertex-connectivity will be at least 2(d + 1)/3.
If the degree is 4 or less, or the graph is also edge-transitive, or the graph is a minimal Cayley graph, then the vertex-connectivity will also be equal to d.
Infinite vertex-transitive graphs include:
infinite paths (infinite in both directions)
infinite regular trees, e.g.
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.
Publications associées (32)
Personnes associées (8)
Concepts associés (18)
Automorphisme de graphe
vignette|On peut définir deux automorphismes sur le graphe maison : l'identité et la permutation qui échange les deux « murs » de la « maison ». En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes. On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe.
Graphe de Cayley
En mathématiques, un graphe de Cayley (du nom d'Arthur Cayley) est un graphe qui encode la structure d'un groupe. C'est un outil important pour l'étude de la combinatoire et de la géométrie des groupes. Étant donné un groupe et une partie génératrice de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit : À chaque élément de , on associe un sommet . À chaque élément de , on associe une couleur . Pour tout et , on trace une arête orientée de couleur du sommet vers le sommet .
Graphe symétrique
En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe : tel que et . En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif. Par définition, un graphe symétrique sans sommet isolé est sommet-transitif et arête-transitif.
Cours associés (3)
MATH-360: Graph theory
The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc
MATH-225: Topology
On étudie des notions de topologie générale: unions et quotients d'espaces topologiques; on approfondit les notions de revêtements et de groupe fondamental,et d'attachements de cellules et on démontre
MATH-213: Differential geometry
Ce cours est une introduction à la géométrie différentielle classique des courbes et des surfaces, principalement dans le plan et l'espace euclidien.
Séances de cours associées (19)
Partitionnement aléatoire de faible diamètre
Discute de la décomposition randomisée à faible diamètre et du partitionnement graphique pour les coupes de bord et la coloration.
Comptage des arbres étiquetés
Explore le comptage des arbres marqués à l'aide de codes et d'algorithmes Prüfer, fournissant des cartes entre les arbres et les séquences.
Cayley Graphs: Propriétés et Applications
Explore les propriétés et les applications des graphes de Cayley en théorie des groupes et en analyse de réseau.