logo

Minimal Cayley graphs

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.

VerticesNo. of min. Cayley graphs
11
21
31
41
51
62
71
83
92
102
111
127
131
142
152
169
171
189
191
208
214
222
231
2437
252
262
277
286
291
3017
311
3255
332
342
352
3653
371
382
394
4040
411
4229
431
447
457
462
471
48275
492
5012
512
5210
531
5478
557
5638
574
582
591
60145
611
622
6316
64728
652
6624
671
6811
692
7022
711
72547
731
742
759
769
772
7837
791
80360
8150
822
831
84196
852
862
872
8846
891
90133
912
9210
934
942
952
Go to top
References

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


Copyright © 2010-2024 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close