[r-t] # Extents on N bells

[Richard Smith]

Chris Poole wrote:

> I was under the impression that it is difficult to prove whether a
> Hamiltonian Cycle exists, but can you count them if you know existence to
> start with??

Not that I'm aware of.

It has been conjectured (by Lovász?) that all Cayley graphs
(and, with finitely many exceptions, all vertex transitive
graphs) have Hamiltonian cycles.

Certainly the relevant graph for ringing (S_N with the set
of changes as generators) is known to be Hamiltonian.
Indeed, there are (linear time) algorithms that will
construct an extent on arbitrarily many bells.  (Plain
changes is the obvious example.)

> Anyway, I've set my brother on to the problem.  Surely his 3 and a bit
> years of graph theory must come in use somewhere!

You should persuade him to join this list.

Richard