A simple graph whose automorphism group is a cyclic group may be termed a cyclic group graph.
Since groups of prime order are always cyclic, any graph with an automorphism group of prime order is a cyclic group graph. In addition, since the automorphism group of the graph complement of any graph is the same as for the original, the graph complement of any cyclic group graph is also a cyclic group graph.
The smallest cyclic group graphs have nine nodes, and these four graphs, which have automorphism group is isomorphic to the cyclic group
C3, are illustrated above. The leftmost graph has the smallest number of edges
and was illustrated by Harary (1994, p. 170), the second graph from the left
is the graph obtained from the -configuration, the third is that configuration's graph
complement, and the fourth is the complement of the first.
Other graphs whose automorphism groups are isomorphic to the cyclic group C3 include three of the Paulus graphs (each on 26 vertices), the 12th fullerene graph on 40 vertices, and Tutte's graph (on 46 vertices).
The smallest simple cyclic group C4 graphs have 10 vertices. There are 12 such graphs, which are illustrated above. Note that the
cyclic group graph with 10 vertices
and 20 edges shown in Fig. 4.8 of Arlinghaus (1985) is not the
graph with the smallest possible number of edges.
The -caveman graph is a
group graph. The following table summarizes some other cyclic
group graphs, where
indicates a
group graph and
is the vertex count.
graph | ||
3 | 9 | |
3 | 24 | Markström graph |
3 | 25 | two 25-Paulus graphs |
3 | 26 | one 26-Paulus graph (and its complement) |
3 | 29 | ten strongly
regular graphs with parameters |
3 | 40 | one 40-fullerene |
3 | 40 | one strongly regular graph with parameters |
3 | 46 | Tutte's graph |
3 | 46 | two 46-fullerenes |
3 | 50 | two 50-fullerenes |
4 | 12 | Nauru configuration graph |
5 | 15 | Cremona-Richmond configuration graph |
5 | 35 | Johnson skeleton graph 47 |
5 | 40 | 40-O'Donnell graph |
5 | 45 | Hochberg-O'Donnell star graph |
5 | 50 | Watkins snark |
5 | 210 | Descartes snark |
6 | 25 | Golomb-Moser graph |
6 | 29 | two strongly
regular graphs with parameters |
7 | 28 | Coxeter configuration graph |
9 | 40 | two strongly regular graphs
with parameters |
12 | 48 | Berman
|
53 | 212 | regular nonplanar graph of degree 5 with diameter 4 |
99 | 198 | regular nonplanar graph of degree 16 with diameter 2 |