Hamiltonicity of Infinite Graphs

Let G be a locally finite infinite graph and let I(G) be the set of ends of G. The Freudenthal compactification of G is the topological space |G| which is obtained from the usual topological space of the graph, when viewed as a 1-dimensional cell complex, by adding all points of I(G) and setting, for each end in I(G), the basic set of neighborhoods of t to consist of sets of the form C(S, t) I(S,t) E'(S,t), where S ranges over the finite subsets of V(G), C(S, t) is the component of G - S containing all rays in t, the set I(S,t) contains all ends in I(G) having rays in C(S, t), and E'(S,t) is the union of half-edges (z,y], one for every edge xy joining S and C(S,t). We define a hamilton circle in |G| as a homeomorphic image C of the unit circle S1 into |G| such that every vertex (and hence every end) of G appears in C. More details about these notions can be found in [1].

A graph G (finite or infinite) is said to be uniquely hamiltonian if it contains precisely one hamilton circle.

For finite graphs, Sheehan proposed the following conjecture in 1975:

Conjecture 1 (Sheehan [3]): If G is a finite r-regular graph, where r > 2, then G is not uniquely hamiltonian.

This conjecture has been proved for all odd values of r [4] and for all even values of r > 23 [2]. By Petersen's theorem, it would suffice to prove it for r = 4.

For infinite graphs, Conjecture 1 is false even for odd values of r, however all known counterexamples (e.g. the two-way infinite ladder) have at least 2 ends. Thus, one can ask if it could be true for 1-ended graphs:

Problem 2: Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree r > 2?

Another possiblility is to ask if conjecture 1 could be true even for graphs with many ends if we assume that (in addition to the vertices) the ends have a certain vertex-degree (the vertex-degree of an end t is the maximal number of disjoint rays in t).

Several other problems about hamilton circles in infinite graphs have been proposed by Georgakopoulos:

Conjecture 3 (Georgakopoulos): If G is a 4-edge-connected locally finite graph, then its line graph is hamiltonian.

This is known for finite graphs. The proof uses the existence of two edge-disjoint spanning trees in 4-edge-connected graphs. In the infinite case, it would be enough to prove that a 4-edge-connected locally finite graph G has two edge-disjoint topological spanning trees (see [1]) one of which is connected as a subgraph of G. The problem is open even for the 1-ended case (where hamilton circles correspond to 2-way-infinite paths).

Conjecture 4 (Georgakopoulos): If the line graph L(G) of a locally finite graph G is 4-connected, then L(G) is hamiltonian.

Conjecture 4 is widely open even in the finite case, where it was proposed by Thomassen [5].

For finite graphs it is well known that the third power of a connected graph is hamiltonian. This has also been proved for locally finite graphs [6]. But what about non-locally-finite graphs?

Conjecture 5 (Georgakopoulos [6]): If G is a countable connected graph then its third power is hamiltonian.

Similarly, one can ask if Fleischner's theorem holds for countable graphs (for locally finite ones it has already been proved [6]):

Conjecture 6 (Georgakopoulos [6]): If G is a 2-connected countable graph then its square is hamiltonian.


[1] R. Diestel, Graph Theory, Third Edition, Springer, 2005.

[2] P. Haxell, B. Seamone, J. Verstraete, Independent dominating sets and hamiltonian cycles, J. Graph Theory 54 (2007) 233-244.

[3] J. Sheehan, The multiplicity of Hamiltonian circuits in a graph. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pp. 477-480. Academia, Prague, 1975.

[4] A.G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs. Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). Ann. Discrete Math. 3 (1978), Exp. No. 13, 3 pp.

[5] C. Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324.

[6] A. Georgakopoulos, Oberwolfach reports, 16/2007.

Send comments to mohar(at)sfu.ca

Revised: August 05, 2007.