1. Cycles through all finite vertex sets in infinite graphs.
- Author
-
Kündgen, André, Li, Binlong, and Thomassen, Carsten
- Subjects
- *
HAMILTONIAN graph theory , *FREUDENTHAL compactification , *INFINITY (Mathematics) , *GEOMETRIC vertices , *BIPARTITE graphs - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF