Recursive Euler and Hamilton paths
Author:
Dwight R. Bean
Journal:
Proc. Amer. Math. Soc. 55 (1976), 385394
MSC:
Primary 02F50; Secondary 05C10
MathSciNet review:
0416888
Fulltext 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.
 [1]
Dwight
R. Bean, Effective coloration, J. Symbolic Logic
41 (1976), no. 2, 469–480. MR 0416889
(54 #4952)
 [2]
Carl
G. Jockusch Jr., Ramsey’s theorem and recursion theory,
J. Symbolic Logic 37 (1972), 268–280. MR 0376319
(51 #12495)
 [3]
Carl
G. Jockusch Jr. and Robert
I. Soare, Π⁰₁ classes and
degrees of theories, Trans. Amer. Math.
Soc. 173 (1972),
33–56. MR
0316227 (47 #4775), http://dx.doi.org/10.1090/S00029947197203162270
 [4]
Carl
G. Jockusch Jr. and Robert
I. Soare, Degrees of members of Π⁰₁ classes,
Pacific J. Math. 40 (1972), 605–616. MR 0309722
(46 #8827)
 [5]
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 0314610
(47 #3161)
 [6]
Alfred
B. Manaster and Joseph
G. Rosenstein, Effective matchmaking and
𝑘chromatic graphs, Proc. Amer. Math.
Soc. 39 (1973),
371–378. MR 0340082
(49 #4838), http://dx.doi.org/10.1090/S00029939197303400822
 [7]
C.
St. J. A. NashWilliams, Decomposition of graphs into twoway
infinite paths, Canad. J. Math. 15 (1963),
479–485. MR 0150754
(27 #741)
 [8]
C.
St. J. A. NashWilliams, Euler lines in infinite directed
graphs, Canad. J. Math. 18 (1966), 692–714. MR 0200197
(34 #96)
 [9]
Oystein
Ore, Theory of graphs, American Mathematical Society
Colloquium Publications, Vol. XXXVIII, American Mathematical Society,
Providence, R.I., 1962. MR 0150753
(27 #740)
 [10]
Hartley
Rogers Jr., Theory of recursive functions and effective
computability, McGrawHill Book Co., New YorkToronto, Ont.London,
1967. MR
0224462 (37 #61)
 [1]
 D. Bean, Effective coloration, J. Symbolic Logic 41 (1976), 1417. MR 0416889 (54:4952)
 [2]
 C. G. Jockusch, Jr., Ramsey's theorem and recursion theory, J. Symbolic Logic 37(1972), 268280. MR 0376319 (51:12495)
 [3]
 C. G. Jockusch, Jr. and R. I. Soare, classes and degrees of theories, Trans. Amer. Math. Soc. 173(1972), 3356. MR47 #4775. MR 0316227 (47:4775)
 [4]
 , Degrees of members of classes, Pacific J. Math. 40(1972), 605616. MR46 #8827. MR 0309722 (46:8827)
 [5]
 A. Manaster and J. Rosenstein, Effective matchmaking (recursion theoretic aspects of a theorem of Philip Hall), Proc. London Math. Soc. (3) 25(1972), 615654. MR47 #3161. MR 0314610 (47:3161)
 [6]
 , Effective matchmaking and chromatic graphs, Proc. Amer. Math. Soc. 39(1973), 371378. MR 0340082 (49:4838)
 [7]
 C. St. J. A. NashWilliams, Decomposition of graphs into twoway infinite paths, Canad. J. Math. 15(1963), 479485. MR27 #741. MR 0150754 (27:741)
 [8]
 , Euler lines in infinite directed graphs, Canad. J. Math. 18(1966), 692714. MR34 #96. MR 0200197 (34:96)
 [9]
 O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ., vol. 38, Amer. Math. Soc., Providence, R. I., 1962. MR27 #740. MR 0150753 (27:740)
 [10]
 H. Rogers, Jr., Theory of recursive functions and effective computability, McGrawHill, New York, 1967. MR37 #61. MR 0224462 (37:61)
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
DOI:
http://dx.doi.org/10.1090/S00029939197604168880
PII:
S 00029939(1976)04168880
Keywords:
Euler path,
Hamilton path,
infinite graph,
algorithm,
recursive function
Article copyright:
© Copyright 1976
American Mathematical Society
