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.

When n is not prime, these graphs can be disconnected, and in general, there will be many different ways to combine isomorphic pieces.

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:

• Cn means the cycle of length n
• Kn  means the complete graph on n vertices
• Km,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.
• Cn+ means the cycle of length n with diagonals. It consists of a cycle Cn, where n is even, and each vertex is also joined to its diametrically opposite vertex. Thus, C6+=K3,3
• Cn(k)  means the cycle of length n with chords of length k. It consists of a cycle Cn in which the ith vertex is also joined to the (i+k)th vertex, for all i. Thus, C6(3) = C6+
• Cn(k+)  means the cycle of length n with alternate chords of length k. It consists of a cycle Cn, 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 ith vertices in the m copies of G induce a copy of H. Eg., GxK2 consists of two copies of G, with corresponding vertices in the two copies joined by an edge (K2)
• 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 ith and jth copies of H. Eg., G[K2] consists of n copies of K2, and corresponding to each edge of G, there is a K2,2 connecting the copies.
• Prism(m)  means CmxK2, 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 Q3 or Prism(4), or C4xK2.
• Octahedron   means the graph of the octahedron. It can also be denoted as L(K4) or ~3K2 or C6(2)
• Icosahedron   means the graph of the icosahedron
• Petersen   means the Petersen graph. It can also be described as ~L(K5). It is ubiquitous.
• Qn  means the n-cube. Q2=C4 and Q3=Cube. In general, Qn = Qn-1xK2.
• trunc(G),  where G is planar, means to truncate G, ie, replace each vertex of degree k by a cycle Ck
• BiDbl(G)   means the bipartite double of G. Make two copies of V(G), call them u1,...,un and v1,...,vn. If uv is an edge of G, then u1v2 and v1u2 are edges of BiDbl(G)
• Dbl(G)   means the double of G. Make 2 copies of G, call them G1 and G2. If uv is an edge of G, then u1v2 and v1u2 are also edges of Dbl(G). It is the same as G[~K2].
• Dbl+(G)   means the double-plus of G. It contains Dbl(G) with the additional edges u1u2. It is the same as G[K2].
• Trpl(G)   means the triple of G. It is similar to Dbl(G). Make 3 copies of G, call them G1, G2, and G3. If uv is an edge of G, then u1v2, u1v3, u2v3, v1u2, v1u3, and v2u3 are also edges of Trpl(G). It is the same as G[~K3].
• 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 = k2 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 K7 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 OctahedronxK2. The numbering is the same as that of B.D. McKay and G. Royle.

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

### The 6-point Transitive Graphs

(updated Apr 30/18)

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

C6, K3,3, Prism3=~C6, Octahedron=C6(2)=~3K2, and K6.

The connected vertex-transitive graphs on 6 vertices.

### The 7-point Transitive Graphs

(updated Apr 30/18)

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

C7, C7(2)=~C7, and K7.

The connected vertex-transitive graphs on 7 vertices.

### The 8-point Transitive Graphs

(updated Apr 30/18)

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

C8, C8+, Cube, K4,4,C8(2)=~C8+,
~Cube, ~C8, ~2C4, ~4K2, K8.

The connected vertex-transitive graphs on 8 vertices.

### The 9-point Transitive Graphs

(updated Apr 30/18)

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

C9, C9(3), C3xC3=L(K3,3), ~C9(3),
~3K3, ~C9, K9.

The connected vertex-transitive graphs on 9 vertices.

### The 10-point Transitive Graphs

(updated May 25/18)

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

C10, Petersen, C10+, Prism5=C5xK2,
~K5xK2, C10(4), C10(2), K5,5,
C10(2,5), C10(4,5), K5xK2, ~Petersen,
~Prism5, ~C10+, ~2C5, ~C10,
~5K2, K10.

The connected vertex-transitive graphs on 10 vertices.

### The 11-point Transitive Graphs

(updated Apr 30/18)

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

C11, C11(3), C11(2), C11(2,5)=~C11(2),
C11(4,5)=~C11(3), ~C11, K11.

The connected vertex-transitive graphs on 11 vertices.

### The 12-point Transitive Graphs

(updated May 25/18)

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

The connected vertex-transitive graphs on 12 vertices.

### The 13-point Transitive Graphs

(updated Apr 30/18)

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

C13, C13(5), C13(3), C13(2), C13(3,4)=Paley(13), C13(2,5), C13(2,6), ~C13(2,5), ~C13(5), ~C13(2), ~C13(3), ~C13, K11.

The connected vertex-transitive graphs on 13 vertices.

### The 14-point Transitive Graphs

(updated May 25/18)

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

The connected vertex-transitive graphs on 14 vertices.

### The 15-point Transitive Graphs

(updated May 25/18)

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

The connected vertex-transitive graphs on 15 vertices.

### The 16-point Transitive Graphs

(updated May 25/18)

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

The connected vertex-transitive graphs on 16 vertices.

### The 17-point Transitive Graphs

(updated Apr 30/18)

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

(updated May 3/18)

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

The connected vertex-transitive graphs on 19 vertices.