Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article

Minimal spanning trees

Author(s): James H. Schmerl
Journal: Proc. Amer. Math. Soc. 132 (2004), 333-340.
MSC (2000): Primary 05C05, 03B30, 03D80
Posted: September 12, 2003
Retrieve article in: PDF DVI PostScript

Abstract | References | Similar articles | Additional information

Abstract: The main result is that a recursive weighted graph having a minimal spanning tree has a minimal spanning tree that is $\Delta^0_2$ . This leads to a proof of the failure of a conjecture of Clote and Hirst (1998) concerning Reverse Mathematics and minimal spanning trees.

References:

1.: Peter G. Clote and Jeffry L. Hirst, Reverse mathematics of some topics from algorithmic graph theory, Fund. Math. 157 (1998), 1-13. MR 99j:03051
2.: Stephen G. Simpson, Subsystems of Second Order Arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 2001i:03126

Similar Articles:

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C05, 03B30, 03D80

Retrieve articles in all Journals with MSC (2000): 05C05, 03B30, 03D80

Additional Information:

James H. Schmerl
Affiliation: Department of Mathematics, University of Connecticut, Storrs, Connecticut, 06269-3009
Email: schmerl@math.uconn.edu

DOI: 10.1090/S0002-9939-03-07182-X
PII: S 0002-9939(03)07182-X
Keywords: Spanning trees, reverse mathematics
Received by editor(s): August 21, 2002
Received by editor(s) in revised form: October 3, 2002
Posted: September 12, 2003
Additional Notes: Thanks to the referee and Jeff Hirst for their help in identifying a serious flaw in the original version of this paper
Communicated by: Carl G. Jockusch, Jr.
Copyright of article: Copyright 2003, American Mathematical Society


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS