Cycles through all finite vertex sets in infinite graphs
| Autor: | Binlong Li, André Kündgen, Carsten Thomassen |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Trémaux tree Foster graph 010102 general mathematics Barnette's conjecture Grinberg's theorem 0102 computer and information sciences 01 natural sciences Complete bipartite graph Hamiltonian path Combinatorics symbols.namesake 010201 computation theory & mathematics symbols Discrete Mathematics and Combinatorics 0101 mathematics Pancyclic graph Hamiltonian path problem Mathematics |
| Zdroj: | European Journal of Combinatorics. 65:259-275 |
| ISSN: | 0195-6698 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect