Janoš Vidali: Automorphism group certificates for cubic vertex-transitive graphs

While datasets of mathematical objects may provide precomputed properties of said objects and thus save the user from expensive computations, verifying their correctness can as expensive, as in the worst case we might have to recompute from scratch. Often we can mitigate this problem by providing certificates which make it possible to verify the properties efficiently. Such certificates may also help import the objects from a dataset into a proof assistant.

We have designed a certificate for the automorphism group of a graph that efficiently certifies the fact that a given permutation group is the full automorphism group of a given graph. We computed the certificates for the combined censuses of connected cubic vertex-transitive graphs on up to 1280 vertices by Potočnik, Spiga and Verret, and of connected cubic symmetric graphs on up to 2048 vertices by Conder. The censuses are available in the DiscreteZOO database. Our certificates can be used to verify further symmetry properties of the graphs, such as vertex- and arc-transitivity.