Vertex-Transitive Graphs

Last update=25 May, 2018

A graph is vertex-transitive if every vertex can be mapped to any other vertex by some automorphism, that is, it is symmetric. The graphs listed here were produced by B.D. McKay's graph generation software. They can also be downloaded from G. Royle's Combinatorial Data website, where they are stored in a compressed "g6-format". They are available here in G&G ascii format. The G&G ascii format contains coordinates of the vertices, giving nice drawings of the graphs, illustrating their structure. Some of these drawings are shown in the G&G Overview.

A vertex-transitive graph is constructed as a union of vertex-transitive "pieces". Each piece is an edge-orbit of a transitive permutation group. For example, an easy case is when n is an odd prime. For then a transitive group acting on n points must have an element of order n, which must be a permutation θ=(1,2,,...,n). The edge orbits of θ are easy to describe: they are the (n-1)/2 orbits generated by the edges {1,2}, {1,3}, {1, 4}, ..., {1, (n+1)/2}. So any vertex-transitive graph on n points, when n is an odd prime, is a union of some of these orbits. Naturally, different unions may result in isomorphic graphs.

The vertex-transitive graphs up to 16 vertices can mostly be described with a simple notation, which is here described. Only the connected vertex transitive graphs are contained here. (But the disconnected ones are here too, disguised as complements of connected graphs.)

Notation:

• C_n means the cycle of length n
• K_n  means the complete graph on n vertices
• K_m,n  means the complete bipartite graph. It has mn vertices
• ~G   means the complement of G
• @G   means the bipartite complement of G, ie, if G has a unique bipartition (X,Y) up to isomorphism, complement the edges between X and Y.
• C_n⁺ means the cycle of length n with diagonals. It consists of a cycle C_n, where n is even, and each vertex is also joined to its diametrically opposite vertex. Thus, C₆⁺=K_3,3
• C_n(k)  means the cycle of length n with chords of length k. It consists of a cycle C_n in which the i^th vertex is also joined to the (i+k)^th vertex, for all i. Thus, C₆(3) = C₆⁺
• C_n(k⁺)  means the cycle of length n with alternate chords of length k. It consists of a cycle C_n, where n is even, and only each even vertex  i  is joined to vertex i+k
• 2G   means two disjoint copies of G
• GxH   means the direct product of G and H. If G has n vertices and H has m vertices, then GxH consists of m copies of G, where the set of i^th vertices in the m copies of G induce a copy of H. Eg., GxK₂ consists of two copies of G, with corresponding vertices in the two copies joined by an edge (K₂)
• G[H]   means the lexicographic product of G and H (also known as the composition of G and H). If G has n vertices and H has m vertices, then G[H] consists of n copies of H, and corresponding to each edge ij of G, there is a complete bipartite graph between the vertices of the i^th and j^th copies of H. Eg., G[K₂] consists of n copies of K₂, and corresponding to each edge of G, there is a K_2,2 connecting the copies.
• Prism(m)  means C_mxK₂, ie, two cycles with corresponding vertices joined by a matching
• L(G)   means the line-graph of G. Its vertices are the edges of G, with two vertices of L(G) being adjacent if the corresponding edges of G share a common endpoint
• Cube   means the graph of the cube. It can also be denoted as Q₃ or Prism(4), or C₄xK₂.
• Octahedron   means the graph of the octahedron. It can also be denoted as L(K₄) or ~3K₂ or C₆(2)
• Icosahedron   means the graph of the icosahedron
• Petersen   means the Petersen graph. It can also be described as ~L(K₅). It is ubiquitous.
• Q_n  means the n-cube. Q₂=C₄ and Q₃=Cube. In general, Q_n = Q_n-1xK₂.
• trunc(G),  where G is planar, means to truncate G, ie, replace each vertex of degree k by a cycle C_k
• BiDbl(G)   means the bipartite double of G. Make two copies of V(G), call them u₁,...,u_n and v₁,...,v_n. If uv is an edge of G, then u₁v₂ and v₁u₂ are edges of BiDbl(G)
• Dbl(G)   means the double of G. Make 2 copies of G, call them G₁ and G₂. If uv is an edge of G, then u₁v₂ and v₁u₂ are also edges of Dbl(G). It is the same as G[~K₂].
• Dbl⁺(G)   means the double-plus of G. It contains Dbl(G) with the additional edges u₁u₂. It is the same as G[K₂].
• Trpl(G)   means the triple of G. It is similar to Dbl(G). Make 3 copies of G, call them G₁, G₂, and G₃. If uv is an edge of G, then u₁v₂, u₁v₃, u₂v₃, v₁u₂, v₁u₃, and v₂u₃ are also edges of Trpl(G). It is the same as G[~K₃].
• antip(G)  means the antipodal graph of G. Each vertex v of G has one or more vertices at maximum possible distance from v, its antipodal vertices. In antip(G), each v is joined to the vertices which are antipodal to it in G.
• Paley(n)  means the Paley graph of order n. The Paley graphs are quadratic residue graphs, a special family of self-complementary graphs. The order n must be a prime power congruent to 1 (mod 4). Vertices i and j are adjacent if   i - j = k² in GF(n) for some k.
• Heawood  means the Heawood graph. It is the incidence graph of the Fano plane, the unique projective plane with 7 points and 7 lines. The Heawood graph is also known as the (3,6)-cage. It is also the dual of the unique embedding of K₇ on the torus, which is likely how Heawood discovered it.
• Clebsch  means the Clebsch graph. It is a strongly regular graph with parameters SR(16,5,0,2), based on the hypercube.
• Shrikande  means the Shrikande graph. It is a strongly regular graph with parameters SR(16,6,2,2) consisting of many interlaced 4-cycles.

Graph Names, Automorphism Groups

The vertex-transitive graphs are named as
VT12_38[96]=~(OctahedronxK2). This means Vertex-Transitive Graph number 38 on 12 points. The automorphism group has order 96 (the number in square brackets). This graph is isomorphic to the complement of OctahedronxK₂. The numbering is the same as that of B.D. McKay and G. Royle.

Download:

Note: Some files were lost as a result of a disk crash in March, 2018. They are being regenerated.

The 6-point Transitive Graphs

There are 5 connected vertex-transitive graphs on 6 vertices:

C₆, K_3,3, Prism3=~C₆, Octahedron=C₆(2)=~3K₂, and K₆.

   The connected vertex-transitive graphs on 6 vertices.

The 7-point Transitive Graphs

There are 3 connected vertex-transitive graphs on 7 vertices:

C₇, C₇(2)=~C₇, and K₇.

   The connected vertex-transitive graphs on 7 vertices.

The 8-point Transitive Graphs

There are 10 connected vertex-transitive graphs on 8 vertices:

C₈, C₈⁺, Cube, K_4,4,C₈(2)=~C₈⁺,
~Cube, ~C₈, ~2C₄, ~4K₂, K₈.

   The connected vertex-transitive graphs on 8 vertices.

The 9-point Transitive Graphs

There are 7 connected vertex-transitive graphs on 9 vertices:

C₉, C₉(3), C₃xC₃=L(K_3,3), ~C₉(3),
~3K₃, ~C₉, K₉.

   The connected vertex-transitive graphs on 9 vertices.

The 10-point Transitive Graphs

There are 18 connected vertex-transitive graphs on 10 vertices:

C₁₀, Petersen, C₁₀⁺, Prism5=C₅xK₂,
~K₅xK₂, C₁₀(4), C₁₀(2), K_5,5,
C₁₀(2,5), C₁₀(4,5), K₅xK₂, ~Petersen,
~Prism5, ~C₁₀⁺, ~2C₅, ~C₁₀,
~5K₂, K₁₀.

   The connected vertex-transitive graphs on 10 vertices.

The 11-point Transitive Graphs

There are 7 connected vertex-transitive graphs on 11 vertices:

C₁₁, C₁₁(3), C₁₁(2), C₁₁(2,5)=~C₁₁(2),
C₁₁(4,5)=~C₁₁(3), ~C₁₁, K₁₁.

   The connected vertex-transitive graphs on 11 vertices.

The 12-point Transitive Graphs

There are 64 connected vertex-transitive graphs on 12 vertices:

   The connected vertex-transitive graphs on 12 vertices.

The 13-point Transitive Graphs

There are 13 connected vertex-transitive graphs on 13 vertices:

C₁₃, C₁₃(5), C₁₃(3), C₁₃(2), C₁₃(3,4)=Paley(13), C₁₃(2,5), C₁₃(2,6), ~C₁₃(2,5), ~C₁₃(5), ~C₁₃(2), ~C₁₃(3), ~C₁₃, K₁₁.

   The connected vertex-transitive graphs on 13 vertices.

The 14-point Transitive Graphs

There are 51 connected vertex-transitive graphs on 14 vertices:

   The connected vertex-transitive graphs on 14 vertices.

The 15-point Transitive Graphs

There are 44 connected vertex-transitive graphs on 15 vertices:

   The connected vertex-transitive graphs on 15 vertices.

The 16-point Transitive Graphs

There are 272 connected vertex-transitive graphs on 16 vertices.

   The connected vertex-transitive graphs on 16 vertices.

The 17-point Transitive Graphs

There are 35 connected vertex-transitive graphs on 17 vertices.

   The connected vertex-transitive graphs on 17 vertices.
Three are self-complementary, including the Paley graph.

The 19-point Transitive Graphs

There are 59 connected vertex-transitive graphs on 19 vertices.

   The connected vertex-transitive graphs on 19 vertices.