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. A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical.

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

• 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

[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

• Godsil, Chris & Royle, Gordon (2001), Algebraic Graph Theory, vol. 207, Graduate Texts in Mathematics, New York: Springer-Verlag .
• Diestel, Reinhard & Leader, Imre (2001), “A conjecture concerning a limit of non-Cayley graphs”, Journal of Algebraic Combinatorics 14: 17–25, <http://www.math.uni-hamburg.de/home/diestel/papers/Cayley.pdf> .
• Eskin, Alex; Fisher, David & Whyte, Kevin (2005), Quasi-isometries and rigidity of solvable groups, arXiv:math.GR/0511647 .