The Vertex-Transitive Graphs on 16 Vertices

Last update=6 Feb, 2009 There are 272 connected vertex-transitive graphs on 16 vertices. A selection of them is shown here. The order of the automorphism group is given in square brackets in each window's title.

Notation:

• Cn means the cycle of length n
• Cn+ means the cycle of length n with diagonals
• Cn(k)  means the cycle of length n with chords of length k
• Cn(k+)  means the cycle of length n with chords of length k from every second vertex
• ~G   means the complement of G
• 2G   means two disjoint copies of G
• GxH   means the direct product of G and H
• L(G)   means the line graph of G
• Q3 and Q4    mean the graphs of the cube and hypercube
• 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 of G, with the additional edges u1u2
• BiDbl(G)   means the bipartite double of G. Make 2 copies of V(G), call them V1 and V2. If uv is an edge of G, then u1v2 and v1u2 are edges of BiDbl(G)
• BiDbl+(G)   means the bipartite double of G, with the additional edges u1u2 for each u in V(G)
• SR(n,k,λ,μ) means a strongly regular graph with n vertices, degree k, and parameters λ and μ

A number of the transitive graphs on 16 vertices can be constructed from 2Q3, two copies of the cube. Then add additional edges. For example Q4, the Clebsch graph, and the Shrikande graph can all be constructed in this fashion. It is possible to chose the vertices of 2Q3 in four groups of four, and induce K4's on these subsets, etc., to obtain a number of vertex-transitive graphs.              Back to the Groups & Graphs home page.