1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gordon Royle Nov 20 '18 at 3:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.