Recursive Euler and Hamilton paths
HTML articles powered by AMS MathViewer
- by Dwight R. Bean PDF
- Proc. Amer. Math. Soc. 55 (1976), 385-394 Request permission
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
- Dwight R. Bean, Effective coloration, J. Symbolic Logic 41 (1976), no. 2, 469–480. MR 416889, DOI 10.2307/2272247
- Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
- Carl G. Jockusch Jr. and Robert I. Soare, $\Pi ^{0}_{1}$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33–56. MR 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- Carl G. Jockusch Jr. and Robert I. Soare, Degrees of members of $\Pi ^{0}_{1}$ classes, Pacific J. Math. 40 (1972), 605–616. MR 309722
- Alfred B. Manaster and Joseph G. Rosenstein, Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall), Proc. London Math. Soc. (3) 25 (1972), 615–654. MR 314610, DOI 10.1112/plms/s3-25.4.615
- Alfred B. Manaster and Joseph G. Rosenstein, Effective matchmaking and $k$-chromatic graphs, Proc. Amer. Math. Soc. 39 (1973), 371–378. MR 340082, DOI 10.1090/S0002-9939-1973-0340082-2
- C. St. J. A. Nash-Williams, Decomposition of graphs into two-way infinite paths, Canadian J. Math. 15 (1963), 479–485. MR 150754, DOI 10.4153/CJM-1963-052-8
- C. St. J. A. Nash-Williams, Euler lines in infinite directed graphs, Canadian J. Math. 18 (1966), 692–714. MR 200197, DOI 10.4153/CJM-1966-070-2
- Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR 0150753
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 55 (1976), 385-394
- MSC: Primary 02F50; Secondary 05C10
- DOI: https://doi.org/10.1090/S0002-9939-1976-0416888-0
- MathSciNet review: 0416888