#jsDisabledContent { display:none; } My Account |  Register |  Help

# Vertex-transitive graph

Article Id: WHEBN0000581175
Reproduction Date:

 Title: Vertex-transitive graph Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

### Vertex-transitive graph

 Graph families defined by their automorphisms distance-transitive \boldsymbol{\rightarrow} distance-regular \boldsymbol{\leftarrow} strongly regular \boldsymbol{\downarrow} symmetric (arc-transitive) \boldsymbol{\leftarrow} t-transitive, t ≥ 2 skew-symmetric \boldsymbol{\downarrow} (if connected) vertex- and edge-transitive \boldsymbol{\rightarrow} edge-transitive and regular \boldsymbol{\rightarrow} edge-transitive \boldsymbol{\downarrow} \boldsymbol{\downarrow} \boldsymbol{\downarrow} vertex-transitive \boldsymbol{\rightarrow} regular \boldsymbol{\rightarrow} (if bipartite) biregular \boldsymbol{\uparrow} Cayley graph \boldsymbol{\leftarrow} zero-symmetric asymmetric

In the mathematical field of graph theory, 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) \rightarrow V(G)\

such that

f(v_1) = v_2.\

In other words, a graph is vertex-transitive if its automorphism group acts transitively upon its vertices.[1] A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical.

Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph).

## Contents

• Finite examples 1
• Properties 2
• Infinite examples 3
• References 5

## Finite examples

The edges of the truncated tetrahedron form a vertex-transitive graph (also a Cayley graph) which is not symmetric.

Finite vertex-transitive graphs include the symmetric graphs (such as the Petersen graph, the Heawood graph and the vertices and edges of the Platonic solids). The finite Cayley graphs (such as cube-connected cycles) are also vertex-transitive, as are the vertices and edges of the Archimedean solids (though only two of these are symmetric). Potočnik, Spiga and Verret have constructed a census of all connected cubic vertex-transitive graphs on at most 1280 vertices.[2]

Although every Cayley graph is vertex-transitive, there exist other vertex-transitive graphs that are not Cayley graphs. The most famous example is the Petersen graph, but others can be constructed including the line graphs of edge-transitive non-bipartite graphs with odd vertex degrees.[3]

## Properties

The edge-connectivity of a vertex-transitive graph is equal to the degree d, while the vertex-connectivity will be at least 2(d+1)/3.[4] If the degree is 4 or less, or the graph is also edge-transitive, or the graph is a minimal Cayley graph, then the vertex-connectivity will also be equal to d.[5]

## Infinite examples

Infinite vertex-transitive graphs include:

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 stated that every infinite vertex-transitive graph is quasi-isometric to a Cayley graph. A counterexample was proposed by Diestel and Leader in 2001.[6] In 2005, Eskin, Fisher, and Whyte confirmed the counterexample.[7]

## References

1. ^ .
2. ^ Potočnik P., Spiga P. and Verret G. (2013), "Cubic vertex-transitive graphs on up to 1280 vertices", Journal of Symbolic Computation 50: 465–477, .
3. ^ Lauri, Josef; Scapellato, Raffaele (2003), Topics in graph automorphisms and reconstruction, London Mathematical Society Student Texts 54, Cambridge: Cambridge University Press, p. 44, . Lauri and Scapelleto credit this construction to Mark Watkins.
4. ^ Godsil, C. and Royle, G. (2001), Algebraic Graph Theory, Springer Verlag
5. ^ Babai, L. (1996), Technical Report TR-94-10, University of Chicago[2]
6. ^ Diestel, Reinhard; .
7. ^ Eskin, Alex; Fisher, David; Whyte, Kevin (2005). "Quasi-isometries and rigidity of solvable groups". .