An undirected graph G is a minimal Cayley graph if there is a group Γ with an inclusion-minimal inverse-closed generating set C such that the Cayley graph Cay(Γ,C) is isomorphic to G. Minimal Cayley graphs are still not well-understood. A very famous problem usually attributed to Lovász [1] asks whether they are all Hamiltonian. Another problem is whether their chromatic number is bounded by a global constant c. Babai has conjectured both that such a constant exists [2] and that it does not exist [3].
Below are the lists of minimal Cayley graphs. These graphs were kindly provided to us by Kolja Knauer who computed them using GAP and SageMath. The graph lists are currently only available in 'graph6' format.
Vertices | No. of min. Cayley graphs |
---|---|
1 | 1 |
2 | 1 |
3 | 1 |
4 | 1 |
5 | 1 |
6 | 2 |
7 | 1 |
8 | 3 |
9 | 2 |
10 | 2 |
11 | 1 |
12 | 7 |
13 | 1 |
14 | 2 |
15 | 2 |
16 | 9 |
17 | 1 |
18 | 9 |
19 | 1 |
20 | 8 |
21 | 4 |
22 | 2 |
23 | 1 |
24 | 37 |
25 | 2 |
26 | 2 |
27 | 7 |
28 | 6 |
29 | 1 |
30 | 17 |
31 | 1 |
32 | 55 |
33 | 2 |
34 | 2 |
35 | 2 |
36 | 53 |
37 | 1 |
38 | 2 |
39 | 4 |
40 | 40 |
41 | 1 |
42 | 29 |
43 | 1 |
44 | 7 |
45 | 7 |
46 | 2 |
47 | 1 |
48 | 275 |
49 | 2 |
50 | 12 |
51 | 2 |
52 | 10 |
53 | 1 |
54 | 78 |
55 | 7 |
56 | 38 |
57 | 4 |
58 | 2 |
59 | 1 |
60 | 145 |
61 | 1 |
62 | 2 |
63 | 16 |
64 | 728 |
65 | 2 |
66 | 24 |
67 | 1 |
68 | 11 |
69 | 2 |
70 | 22 |
71 | 1 |
72 | 547 |
73 | 1 |
74 | 2 |
75 | 9 |
76 | 9 |
77 | 2 |
78 | 37 |
79 | 1 |
80 | 360 |
81 | 50 |
82 | 2 |
83 | 1 |
84 | 196 |
85 | 2 |
86 | 2 |
87 | 2 |
88 | 46 |
89 | 1 |
90 | 133 |
91 | 2 |
92 | 10 |
93 | 4 |
94 | 2 |
95 | 2 |
[1] László Lovász, Combinatorial problems and exercises, American Mathematical Society, 2007.
[2] László Babai, Chromatic number and subgraphs of Cayley graphs, Theory and Applications of Graphs, in Proc. Kalamazoo 1976, Lect. Notes Math., vol. 642, pp. 10-22, 1978.
[3] László Babai, Automorphism groups, isomorphism, reconstruction, in Handbook of Combinatorics, vol. 1-2, pages 1447–1540, Elsevier (North-Holland), 1995.