Vertex-transitive graph

From Wikipedia, the free encyclopedia

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 1 Finite examples 2 Infinite examples 3 Infinite vertex-transitive graphs 4 See also 5 References

[edit] Finite examples

• Kneser graph and its complement Johnson graph
  • Petersen graph
• finite Cayley graphs
  • circulant graphs
    • Heawood graph
    • Complete graph
    • Cycle graph
    • Complete bipartite graph K_n,n
• graphs of Platonic solids and Archimedean solids

[edit] 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

[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 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.

[edit] See also

• Edge-transitive graph
• Lovász conjecture

[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.
• Alex Eskin, David Fisher and Kevin Whyte, Quasi-isometries and rigidity of solvable groups, arXiv preprint math.GR/0511647.