Abstract
A closed curve in the Freudenthal compactification |G| of an infinite locally finite graph G is called a Hamiltonian curve if it meets every vertex of G exactly once (and hence it meets every end at least once). We prove that |G| has a Hamiltonian curve if and only if every finite vertex set of G is contained in a cycle of G. We apply
this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve.
this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve.
Original language | English |
---|---|
Journal | European Journal of Combinatorics |
Volume | 65 |
Pages (from-to) | 259–275 |
ISSN | 0195-6698 |
DOIs | |
Publication status | Published - 2017 |