VertexTransitive Graphs
Last update=25 May, 2018
A graph is vertextransitive 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 "g6format". 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 vertextransitive graph is constructed as a union of vertextransitive
"pieces". Each piece is an edgeorbit 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 (n1)/2 orbits generated by the edges {1,2}, {1,3}, {1, 4}, ..., {1, (n+1)/2}.
So any vertextransitive 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 vertextransitive 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_{6}^{+}=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_{6}(3) = C_{6}^{+}
 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_{2} consists
of two copies of G, with corresponding vertices in the two copies joined by an edge (K_{2})
 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_{2}] consists
of n copies of K_{2}, and corresponding to each edge of G, there is a K_{2,2}
connecting the copies.
 Prism(m)^{ } means C_{m}xK_{2}, ie, two cycles with corresponding vertices joined by a matching
 L(G)^{ }_{ } means the linegraph 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_{3} or Prism(4), or C_{4}xK_{2}.
 Octahedron^{ }_{ } means the graph of the octahedron.
It can also be denoted as L(K_{4}) or ~3K_{2} or C_{6}(2)
 Icosahedron^{ }_{ } means the graph of the icosahedron
 Petersen^{ }_{ } means the Petersen graph. It can also be
described as ~L(K_{5}). It is ubiquitous.
 Q_{n}^{ } means the ncube. Q_{2}=C_{4}
and Q_{3}=Cube. In general, Q_{n} = Q_{n1}xK_{2}.
 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_{1},...,u_{n} and v_{1},...,v_{n}.
If uv is an edge of G, then u_{1}v_{2} and v_{1}u_{2} are edges of BiDbl(G)
 Dbl(G)^{ }_{ } means the double of G. Make 2 copies of G,
call them G_{1} and G_{2}. If uv is an edge of G, then u_{1}v_{2}
and v_{1}u_{2} are also edges of Dbl(G). It is the same as G[~K_{2}].
 Dbl^{+}(G)^{ }_{ } means the doubleplus of G.
It contains Dbl(G) with the additional edges u_{1}u_{2}. It is the same as G[K_{2}].
 Trpl(G)^{ }_{ } means the triple of G. It is similar to
Dbl(G). Make 3 copies of G, call them G_{1}, G_{2}, and G_{3}. If uv is an
edge of G, then u_{1}v_{2}, u_{1}v_{3}, u_{2}v_{3},
v_{1}u_{2}, v_{1}u_{3}, and v_{2}u_{3} are also edges of Trpl(G).
It is the same as G[~K_{3}].
 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 selfcomplementary graphs. The order n must be
a prime power congruent to 1 (mod 4). Vertices i and j are adjacent if i  j = k^{2} 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_{7} 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 4cycles.
Graph Names, Automorphism Groups
The vertextransitive graphs are named as
VT12_38[96]=~(OctahedronxK2).
This means VertexTransitive 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_{2}.
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 6point Transitive Graphs (updated Apr 30/18)
There are 5 connected vertextransitive graphs on 6 vertices:
C_{6}, K_{3,3}, Prism3=~C_{6}, Octahedron=C_{6}(2)=~3K_{2}, and K_{6}.
The connected vertextransitive graphs on 6 vertices.
The 7point Transitive Graphs (updated Apr 30/18)
There are 3 connected vertextransitive graphs on 7 vertices:
C_{7}, C_{7}(2)=~C_{7}, and K_{7}.
The connected vertextransitive graphs on 7 vertices.
The 8point Transitive Graphs (updated Apr 30/18)
There are 10 connected vertextransitive graphs on 8 vertices:
C_{8}, C_{8}^{+}, Cube, K_{4,4},C_{8}(2)=~C_{8}^{+},
~Cube, ~C_{8}, ~2C_{4},
~4K_{2}, K_{8}.
The connected vertextransitive graphs on 8 vertices.
The 9point Transitive Graphs (updated Apr 30/18)
There are 7 connected vertextransitive graphs on 9 vertices:
C_{9}, C_{9}(3), C_{3}xC_{3}=L(K_{3,3}), ~C_{9}(3),
~3K_{3}, ~C_{9}, K_{9}.
The connected vertextransitive graphs on 9 vertices.
The 10point Transitive Graphs (updated May 25/18)
There are 18 connected vertextransitive graphs on 10 vertices:
C_{10}, Petersen, C_{10}^{+}, Prism5=C_{5}xK_{2},
~K_{5}xK_{2}, C_{10}(4), C_{10}(2), K_{5,5},
C_{10}(2,5), C_{10}(4,5), K_{5}xK_{2}, ~Petersen,
~Prism5, ~C_{10}^{+}, ~2C_{5}, ~C_{10}, ~5K_{2}, K_{10}.
The connected vertextransitive graphs on 10 vertices.
The 11point Transitive Graphs (updated Apr 30/18)
There are 7 connected vertextransitive graphs on 11 vertices:
C_{11}, C_{11}(3), C_{11}(2), C_{11}(2,5)=~C_{11}(2),
C_{11}(4,5)=~C_{11}(3), ~C_{11}, K_{11}.
The connected vertextransitive graphs on 11 vertices.
The 12point Transitive Graphs (updated May 25/18)
There are 64 connected vertextransitive graphs on 12 vertices:
The connected vertextransitive graphs on 12 vertices.
The 13point Transitive Graphs (updated Apr 30/18)
There are 13 connected vertextransitive graphs on 13 vertices:
C_{13}, C_{13}(5), C_{13}(3), C_{13}(2),
C_{13}(3,4)=Paley(13), C_{13}(2,5), C_{13}(2,6), ~C_{13}(2,5), ~C_{13}(5), ~C_{13}(2), ~C_{13}(3), ~C_{13}, K_{11}.
The connected vertextransitive graphs on 13 vertices.
The 14point Transitive Graphs (updated May 25/18)
There are 51 connected vertextransitive graphs on 14 vertices:
The connected vertextransitive graphs on 14 vertices.
The 15point Transitive Graphs (updated May 25/18)
There are 44 connected vertextransitive graphs on 15 vertices:
The connected vertextransitive graphs on 15 vertices.
The 16point Transitive Graphs (updated May 25/18)
There are 272 connected vertextransitive graphs on 16 vertices.
The connected vertextransitive graphs on 16 vertices.
The 17point Transitive Graphs (updated Apr 30/18)
There are 35 connected vertextransitive graphs on 17 vertices.
The connected vertextransitive graphs on 17 vertices.
Three are selfcomplementary, including the Paley graph.
The 19point Transitive Graphs (updated May 3/18)
There are 59 connected vertextransitive graphs on 19 vertices.
The connected vertextransitive graphs on 19 vertices.
Back to the Groups & Graphs home page.
