Vol. 17, No. 2, 1966

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author index
To appear
Other MSP journals
Paths on polyhedra. II

Victor Klee

Vol. 17 (1966), No. 2, 249–262

Continuing the author’s earlier investigation, this paper studies the behavior of paths on (convex) polyhedra relative to the facets of the polyhedra. In Section 1, the polytopes which are polar to the cyclic polytopes are shown to admit Hamiltonian circuits, and the fact that they do leads to sharp upper bounds for the lengths of simple paths or simple circuits on polyhedra of a given dimension having a given number of facets. Section 2 is devoted to the conjecture, due jointly to Philip Wolfe and the author, that any two vertices of a polytope can be joined by a path which never returns to a facet from which it has earlier departed. This implies a well-known conjecture of Warren Hirsch, asserting that n d is an upper bound for the diameter of d-dimensional polytopes having n facets. The Wolfe-Klee conjecture is proved here for 3-dimensional polyhedra, and a stronger conjecture (dealing with polyhedral cell-complexes) is established for certain special cases.

Mathematical Subject Classification
Primary: 52.10
Received: 19 November 1964
Published: 1 May 1966
Victor Klee
University of Washington
United States