At the moment I am interested in maximal non-hamiltonian graphs, so that is a (simple, undirected) graph that does not itself have a hamilton cycle, but if you add an edge between any two distinct non-adjacent vertices, then this creates one. Equivalently, the graph has a hamilton path connecting any two distinct non-adjacent vertices, but no hamilton cycle.

There are a (very) few results around, both old and somewhat new, but I would very much like to know what became of a line of research whose existence I only know from a couple of seminar announcements. The announcement here http://www.columbia.edu/~mc2775/moulton.pdf (which conveniently does not include the speaker's name) mentions a conjecture that a 2-connected maximal non-hamiltonian graph is spanned by a theta graph, and also that this is proved for order up to 20.

The similar announcement here (https://www.math.princeton.edu/events/maximal-non-hamiltonian-graphs-2014-02-27t213002) indicates that the author is David Moulton, someone who worked (or perhaps still works) at a Princeton place called IDACCR. But IDACCR seems to be some semi-secret crypto-research place where you need a high security clearance, and so there is certainly nothing like an "Our People" link on their three-page website. I think that perhaps the author has left academia, but that's just guessing from Googling the name.

If anyone knows whether this research ever appeared, or if someone on MO went to one of these seminars and took some notes, or even just remembers anything, or if anyone knows the author and could drop him an email letting him know someone is interested in this work, then I'd appreciate it.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.