Hamilton decompositions of two-ended infinite graphs

I recently submitted my honours thesis, and for posterity (or anybody who might actually be interested) it is available for download as a PDF here.

jack_neubecker_thesis_nov_2020 Download

Abstract

A Cayley graph $Cay(\Gamma, S)$ is a graph with vertex set the elements of the group $\Gamma$ , and edge set $\{\{u,v\} \mid v = u + s, s \in S \subset \Gamma\}$ . A Hamilton cycle is a closed path which visits every vertex in a graph exactly once, and a Hamilton decomposition of a graph is a partition of its edge-set into Hamilton cycles. It has been conjectured by Alspach that every connected $2k$ -regular Cayley graph of a finite abelian group has a Hamilton decomposition. Another conjecture from Alspach and Rosenfeld says that if $G$ is a 3-connected, 3-regular graph with a Hamilton cycle, then the Cartesian product $G \square K_2$ is Hamilton decomposable. Bermond also conjectures that if two graphs are Hamilton decomposable, then their Cartesian product is also Hamilton decomposable. These three conjectures remain open, and we examine their infinite generalisations. Specifically, we study two-ended infinite abelian groups, and the Cartesian product $G \square P_\infty$ , where $G$ is an even-regular finite graph and $P_\infty$ is a two-way infinite path. The notion of a Hamilton cycle can be generalised to infinite graphs as a spanning two-way infinite path. However, if the graph has two ends, some graphs contain an end-separating edge-cut which differs in parity from the number of paths in the decomposition, precluding the existence of a decomposition into spanning two-way infinite paths. The question, then, is whether this is the only obstruction to a Hamilton decomposition. We show that if $G$ is 2, 4, or 6-regular, and has a Hamilton decomposition, then $G \square P_\infty$ has a Hamilton decomposition if it avoids the obstruction. We show that a two-ended Cayley graph with only one non-torsion generating element can be viewed as a graph of the form $G \square P_\infty$ , and thus complete the case of the generalisation of Alspach’s conjecture for two-ended, 6-regular Cayley graphs of infinite abelian groups with only one non-torsion generating element. We further investigate the existence of a Hamilton decomposition of $G \square P_\infty$ if $G$ has a Hamilton cycle, but not a Hamilton decomposition, and construct a backtracking algorithm to test the generalisation of Alspach’s conjecture and our techniques, in the cases which remain unproven. An infinite family of positive solutions is provided in this unproven case, as well as examples which do not fit the techniques used.

Keywords

Hamilton cycle, Hamilton decomposition, graph, Cayley graph, Hamilton double-ray, Alspach’s Conjecture, Bermond’s Conjecture, Alspach and Rosenfeld’s Conjecture, infinite graph, locally finite graph.

Abstract

Keywords

Share this: