Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Recursive Euler and Hamilton paths

Author: Dwight R. Bean
Journal: Proc. Amer. Math. Soc. 55 (1976), 385-394
MSC: Primary 02F50; Secondary 05C10
MathSciNet review: 0416888
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We employ recursion theoretic arguments to show that Hamilton paths for locally finite graphs are more difficult to find, in general, than Euler paths. A locally finite graph is recursive if we can effectively decide whether or not any two given vertices are adjacent, and highly recursive if we can effectively find all vertices adjacent to any given vertex. We find that there are recursive planar graphs with Euler or Hamilton paths but no such recursive paths. There are even particularly simple classes of connected, planar, highly recursive graphs for which we can show there is no effective way to decide about the existence of Euler or Hamilton paths. However, we obtain the following contrast: If a highly recursive graph has an Euler path we can effectively find a recursive Euler path; whereas, there is a planar, highly recursive graph with Hamilton paths but no recursive Hamilton path.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 02F50, 05C10

Retrieve articles in all journals with MSC: 02F50, 05C10

Additional Information

Keywords: Euler path, Hamilton path, infinite graph, algorithm, recursive function
Article copyright: © Copyright 1976 American Mathematical Society