Vertex-Transitive Graphs

Last update=21 Feb, 2009
G&G

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 binary and text formats. The G&G binary files contain nice drawings of the graphs, illustrating their structure. These drawings are also shown in the G&G Overview.

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
  • 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 2 copies of G, with corresponding vertices in the 2 copies joined by an edge (K2)
  • 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 2 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 2 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)
  • Dbl+(G)   means the double-plus of G. It contains Dbl(G) with the additional edges u1u2
  • 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)
  • 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 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 basically 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. MacKay and G. Royle.

hr

Download:

Note: Stuffit Expander may be necessary to unpack these files. It is a free download.

The 6-point Transitive Graphs

There are 5 connected vertex-transitive graphs on 6 vertices:
C6, K3,3, Prism3=~C6, Octahedron=C6(2)=~3K2, and K6.

GraphIcon    The connected vertex-transitive graphs on 6 vertices.

The 7-point Transitive Graphs

There are 3 connected vertex-transitive graphs on 7 vertices:
C7, C7(2)=~C7, and K7.

GraphIcon    The connected vertex-transitive graphs on 7 vertices.

The 8-point Transitive Graphs

There are 10 connected vertex-transitive graphs on 8 vertices:
C8, C8+, Cube, K4,4,
C8(2)=~C8+, ~Cube, ~C8, ~2C4,
~4K2, K8.

GraphIcon    The connected vertex-transitive graphs on 8 vertices.

The 9-point Transitive Graphs

There are 7 connected vertex-transitive graphs on 9 vertices:
C9, C9(3), C3xC3=L(K3,3), ~C9(3),
~3K3, ~C9, K9.

GraphIcon    The connected vertex-transitive graphs on 9 vertices.

The 10-point Transitive Graphs

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.

GraphIcon    The connected vertex-transitive graphs on 10 vertices.

The 11-point Transitive Graphs

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.

GraphIcon    The connected vertex-transitive graphs on 11 vertices.

The 12-point Transitive Graphs

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

GraphIcon    The connected vertex-transitive graphs on 12 vertices.

The 13-point Transitive Graphs

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.

GraphIcon    The connected vertex-transitive graphs on 13 vertices.

The 14-point Transitive Graphs

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

GraphIcon    The connected vertex-transitive graphs on 14 vertices.

The 15-point Transitive Graphs

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

GraphIcon    The connected vertex-transitive graphs on 15 vertices.

The 16-point Transitive Graphs

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

GraphIcon    The connected vertex-transitive graphs on 16 vertices.

The 17-point Transitive Graphs

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

GraphIcon    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.

GraphIcon    The connected vertex-transitive graphs on 19 vertices.

hr

Locate to the ftp server to download the text form of these graphs. The text format does not contain drawings of the graphs. It contains adjacencies only.

hrule

G&G     Back to the Groups & Graphs home page.