Vertex-transitive graph

From Wikipedia, the free encyclopedia

Some graph families defined by their automorphisms
distance-transitive		distance-regular
symmetric (arc-transitive)		edge-transitive
(if connected)
vertex-transitive		Cayley graph
regular

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 symmetric 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
• the Rado graph

[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
• Semi-symmetric graph

[edit] References

• Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, 207, 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, doi:10.1023/A:1011257718029, 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, arΧiv:math.GR/0511647 .