VERTEX-TRANSITIVE GRAPH

In mathematics, a 'vertex-transitive graph' is a graph ''G'' such that, given any two vertices v₁ and v₂ of ''G'', there is some automorphism
:''f'' : ''V(G)'' → ''V(G)''
such that
:''f'' (v₁) = v₂.
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 without isolated vertices is also
vertex-transitive.

Contents

Finite examples

Infinite examples

Infinite vertex-transitive graphs

See also

References

Finite examples

★ Heawood graph

★ Kneser graph and its complement Johnson graph

★
★ Petersen graph

★ finite Cayley graphs

★
★ circulant graphs

★
★
★ Complete graph

★
★
★ Cycle graph

★
★
★ Complete bipartite graph $K\_\{n,n\}$

★ graphs of Platonic solids and Archimedean solids

Infinite examples

★ infinite path (infinite in both directions)

★ 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

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 graph is quasi-isometric to a Cayley graph. A counterexample has been proposed by Diestel and Leader. Most recently, Eskin, Fisher, and Whyte confirmed the counterexample.

See also

★ Edge-transitive graph

★ Lovász conjecture

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.

★ Alex Eskin, David Fisher and Kevin Whyte, ''Quasi-isometries and rigidity of solvable groups'', arXiv preprint math.GR/0511647.