Vertex-transitive graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism
such that
In other words, a graph is vertex-transitive if its automorphism group acts transitively upon its vertices.[1] 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).
Contents
Finite examples
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.[2]
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.[3]
Properties
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.[4] 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.[5]
Infinite examples
Infinite vertex-transitive graphs include:
- infinite paths (infinite in both directions)
- infinite regular trees, e.g. the Cayley graph of the free group
- graphs of uniform tessellations (see a complete list of planar tessellations), including all tilings by regular polygons
- infinite Cayley graphs
- the Rado graph
Two countable vertex-transitive graphs are called quasi-isometric if the ratio of their distance functions is bounded from below and from above. A well known conjecture stated that every infinite vertex-transitive graph is quasi-isometric to a Cayley graph. A counterexample was proposed by Diestel and Leader in 2001.[6] In 2005, Eskin, Fisher, and Whyte confirmed the counterexample.[7]
See also
References
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
- ↑ Lua error in package.lua at line 80: module 'strict' not found.. Lauri and Scapelleto credit this construction to Mark Watkins.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.[1]
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
- ↑ Lua error in package.lua at line 80: module 'strict' not found..
External links
- Weisstein, Eric W., "Vertex-transitive graph", MathWorld.
- A census of small connected cubic vertex-transitive graphs . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.