Vertex-transitive graph
From Free net encyclopedia
(Redirected from Vertex-transitive)
Contents |
[edit]
Definition
In mathematics, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism
- f : V(G) → V(G)
such that
- f (v1) = v2.
In other words, a graph is vertex-transitive if its automorphism group acts transitively upon its vertices.
Every vertex-transitive graph is regular. Every arc-transitive graph is also vertex-transitive.
[edit]
Finite examples
- Petersen graph
- Heawood graph
- Complete graph
- Cycle graph
- Complete bipartite graph <math>K_{n,n}</math>
- Kneser graph and its complement Johnson graph
- graphs of Platonic solids and Archimedean solids
- finite Cayley graphs
[edit]
Infinite examples
- infinite path
- infinite regular tree, 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
[edit]
Infinite vertex-transitive graphs
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 states that every infinite vertex-transitive graphs is quasi-isometric to a Cayley graph. A counterexample has been proposed by Diestel and Leader, but the problem remains open.
[edit]
See also
[edit]
References
- Chris Godsil and Gordon Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York, 2001.
- Reinhard Diestel and Imre Leader, A conjecture concerning a limit of non-Cayley graphs, J. Algebraic Combinatorics, Vol. 14 (2001), 17-25.Template:Combin-stub