Skip to content

Two problems on Hamilton cycles

February 1, 2012

Michael’s last post on cubic vertex-transitive graphs mentioned, almost in passing, that every graph in the new catalogue has been checked to see whether it contains a Hamilton cycle – in other words, a cycle passing through each vertex exactly once.

The reason to check this particular property is a very famous and very perplexing conjecture:

Conjecture: Every connected vertex-transitive graph, other than K_2, the Petersen graph P, the Coxeter graph C and the two graphs obtained from P and C by replacing each vertex with a triangle, has a Hamilton cycle.

Naturally enough, the five graphs in the statement are the only vertex-transitive graphs that are known to not have Hamilton cycles. Of these, K_2 can be viewed as a triviality and ignored, but none of the others are Cayley graphs. So a related conjecture is often expressed as follows:

Conjecture: Every connected Cayley graph has a Hamilton cycle.

I don’t know who actually first stated these as conjectures – certainly Lovász made a much weaker conjecture about transitive graphs having Hamilton paths, but I’m not sure whether he made these stronger conjectures.

As Cayley graphs are so intimately related to groups, the second problem can be — and has been — attacked by focussing on one family of groups or another, and in this way a considerable number of infinite families of groups are known to produce only Hamiltonian connected Cayley graphs. Dave Morris (né Witte, assuming né is the masculine of née), who visited us last year, is responsible for several of these and gave us an entertaining talk about the problem.

The class of cubic vertex-transitive graphs is of particular interest because obviously fewer edges makes for fewer cycles so, if there is a counterexample, then looking among cubic graphs is the obvious place to start.  Interestingly though, as far as I know, it has not actually been shown that the truth of either of the two conjectures can be reduced to solving them for cubic graphs. (In other words, while it seems unlikely, there might be a 4-regular counterexample or a 10^{10}-regular counterexample, but no 3-regular one.)

Anyway, we now know that for cubic vertex-transitive graphs, both conjectures are true up to 1280 vertices. The conjectures are interesting because, other than our inability to find counterexamples, there seems no particular reason to believe they are true. There doesn’t seem to be any convincing qualitative argument for why vertex-transitivity should be correlated with Hamiltonicity, and the need for a proof to somehow involve both P and C and the graphs derived from them implies that proving the first conjecture might be quite intricate.

But suppose that someone comes along with a cubic vertex-transitive graph on, say, a million vertices. If it is not Hamiltonian, how would you ever show it? Showing that a graph is Hamiltonian is usually done by heuristically finding a Hamilton cycle, but I suspect that the heuristics for cubic vertex-transitive graphs work well only because these graphs have lots of Hamilton cycles. (I haven’t actually checked this numerically yet.) To prove that a graph doesn’t have a Hamilton cycle either needs an exhaustive computer search, or to use some sort of clever indirect argument or trick. In complexity theory terms, HAMILTONIAN GRAPH is a problem in NP but not (known to be) in co-NP and this is one problem where it may really bite.

The second problem I wanted to discuss on Hamilton cycles is also about regular graphs, but in this case 4-regular graphs with no requirement for vertex-transitivity, and it is usually known as Sheehan’s Conjecture.

Conjecture (Sheehan): Every 4-regular graph with at least one Hamilton cycle has at least two.

One assumes this was inspired by the famous result that every edge in a cubic graph has an even number of Hamilton cycles through it, for which there is a beautiful parity-based proof, and so a cubic graph cannot have just one Hamilton cycle.

The result for cubic graphs works because, ultimately, it can be used to start with one Hamilton cycle and transform it into a different one. So why can’t a similar result be proved for quartic graphs?

Looking at computational data suggests that there are actually lots and lots of Hamilton cycles in quartic graphs (or zero). In fact, the smallest non-zero number of Hamilton cycles in the quartic graphs on 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 and 15 vertices is 12, 16, 23, 29, 36, 36, 48, 60, 72, 72 and 72 respectively. So while there seem to be plenty of “second Hamilton cycles”, at the moment they just appear to be “there by accident” rather than being forced to be there by the existence of the first one.

Of course, this problem has attracted lots of attention – in particular Thomassen proved that a 300-regular graph with a Hamilton cycle has a second one, and the 300 has been successively reduced and is now down, I believe, to 22.

Advertisements
4 Comments leave one →
  1. Alice permalink
    February 2, 2012 10:41 am

    Né is the masculine of née indeed, Gordon.

  2. February 2, 2012 5:39 pm

    “I don’t know who actually first stated these as conjectures – certainly Lovász made a much weaker conjecture about transitive graphs having Hamilton paths, but I’m not sure whether he made these stronger conjectures.”

    From what I have read Lovász didn’t make any of those conjectures. He stated as a an open problem that one should construct additional non-hamiltonian vertex transitive graphs, in addition to the ones in your list here. Some years later he was asked about “his” conjecture that these were the only non-hamiltonian ones and thought it was an unexpected conjecture, which he had not made

    • Gordon Royle permalink*
      February 2, 2012 6:47 pm

      Interesting.. it seems that many “named conjectures” were never actually made by the person whose name is attached to it. In fact, isn’t Wagner’s conjecture that any infinite set of graphs contains two minor-related graphs another one of these “conjectures never made by the author”.

      • February 3, 2012 8:14 pm

        The original referene for Lovasz’s problem is
        Combinatorial structures and their applications.
        Proceedings of the Calgary International Conference on Combinatorial Structures and their Applications held at the University of Calgary, Calgary, Alberta, Canada, June, 1969. Edited by Richard Guy, Haim Hanani, Norbert Sauer and Johanan Schönheim Gordon and Breach, Science Publishers, New York-London-Paris 1970 xvi+508 pp.

        In contrast Babai has conjectured that for any epsilon>0 there is a vertex transitive graph on n vertices with no cycle of length greater than (1-epsilon)n

        László Babai, Automorphism groups, isomorphism, reconstruction, Handbook of combinatorics,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: