Two problems on Hamilton cycles

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.

Continue reading “Two problems on Hamilton cycles”

Cubic vertex-transitive graphs

A graph is called vertex-transitive if for every pair of vertices there is an automorphism of the graph that maps the first to the second. I discussed such graphs and other symmetry classes of graphs in two earlier posts. (I see that I had promised a third in that series but that has yet to eventuate.)

A cubic graph is a graph for which every vertex has valency three, that is, every vertex has exactly three neighbours.  Cubic graphs have been extensively investigated with many graph properties first investigated in the cubic case. For example,  s-arc-transitive graphs were first investigated in the cubic case in the seminal work of William Tutte in two papers in 1947 and 1959.

An arc of a graph is an ordered pair of adjacent vertices and we say that a graph is called arc-transitive if the automorphism group of the graph acts transitively on the set of arcs. The most famous example is the Petersen graph. Arc-transitive graphs are also called symmetric graphs.  Ronald Foster began compiling a list of symmetric cubic graphs in 1932 and this is now known as the Foster census. Marston Conder and Peter Dobcsanyi  extended the census so that it was complete for graphs with at most 768 vertices and Marston has extended it further to include all graphs with at most 2048 vertices. The graphs are available on Marston’s website.

For vertex-transitive cubic graphs there is data collated by Gordon and Brendan McKay that is complete for all graphs with up to 94 vertices as well as all graphs with n vertices for many values of n at most 258. Recently, Primoz Potocnik, Pablo Spiga and Gabriel Verret have comprehensively smashed this upper bound by compiling a list of all vertex-transitive cubic graphs with at most 1280 vertices. This continues the excellent work in graph symmetry that they have been doing in recent years. They have set up a webpage containing the data and a preprint is on the arxiv explaining their methods. I am sure it will be a valuable resource for investigating graphs and testing conjectures. They have already checked that apart from the four known exceptions they each have a Hamiltonian cycle.

As part of their work they have also compiled a list of all arc-transitive graphs of valency 4 on at most 640 vertices. That is also available on their webpage. Primoz is also undertaking a project with Steve Wilson aiming to list all edge-transitive valency 4 graphs on up to 512 vertices. The data so far is available here.

Up ↑