Hamiltonian paths in infinite graphs

DOI10.1007/BF02773868zbMath0756.05073MaRDI QIDQ1196345

David Harel

Publication date: 9 December 1992

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian pathsinfinite graphsrecursive treesinfinite pathshighly undecidablerecursive graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Decidability of theories and sets of sentences (03B25) Connectivity (05C40)

Related Items (10)

Understanding chicken walks on n × n grid: Hamiltonian paths, discrete dynamics, and rectifiable paths ⋮ Infinite versions of some problems from finite complexity theory ⋮ Unbounded search and recursive graph problems ⋮ Linear constraint query languages expressive power and complexity ⋮ 1994–1995 Winter Meeting of the Association for Symbolic Logic ⋮ Is the spiral effect psychological? ⋮ \(A\)-computable graphs ⋮ Domatic partitions of computable graphs ⋮ Computing planarity in computable planar graphs ⋮ Some natural decision problems in automatic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Some undecidable problems involving the edge-coloring and vertex-coloring of graphs
• On the strength of König's duality theorem for infinite bipartite graphs
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• Recursive Euler and Hamilton Paths
• Effective coloration
• Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)

This page was built for publication: Hamiltonian paths in infinite graphs