# Constructing all non-isomorphic Hamiltonian graphs on n vertices

I've recently been taking a combinatorics class and have become interested in Hamiltonian graphs.

This OEIS entry lists the number of Hamiltonian graphs on $$n$$ vertices up to $$n =12$$. However, I am having difficulty finding how these numbers were found. Is it naive to expect an algorithm which actually constructs all the hamiltonian graphs (at least for $$n$$ not too large) to exist?

Thanks.

## 2 Answers

I expect by constructing all graphs, probably using Brendan McKay’s program “geng” and extracting the Hamiltonian ones. Needs quite a few computer cores to do n=12, and I wouldn’t try 13.

The 'filter' approach of generating all non-isomorphic graphs on $$n$$ vertices is the simplest possibility.

The OEIS entry references McKay (1996), but I can't see a paper in this list : https://users.cecs.anu.edu.au/~bdm/publications.html for Hamiltonian graphs (only _hypo_hamiltonian graphs).

Presumably a more efficient approach than filtering would be to extend a Hamiltonian graph on $$n$$ vertices to one on $$n + 1$$ vertices, but maybe that is not possible.

• There are plenty of ways to do a non-filtering search: for $n=12$ you could start with a 12-cycle and then add edges one at a time, thereby creating a list of all the hamiltonian graphs on 12 edges, 13 edges, 14 edges and so on. The isomorph rejection would need to be smart though. – Gordon Royle Nov 20 '18 at 3:08