Accession Number : AD0609571

Title :   PATHS IN POLYHEDRA. I,

Corporate Author : BOEING SCIENTIFIC RESEARCH LABS SEATTLE WASH

Personal Author(s) : Klee,Victor

Report Date : OCT 1964

Pagination or Media Count : 34

Abstract : Further study was made into the behavior of paths in polyhedra relative to the number of facets. Section I, on longest simple paths and circuits, asserts that polytopes which are 'polar' (or 'combinatorially dual') to the cyclic polytopes all admit Hamiltonian circuits. This leads to a sharp upper bound for the lengths of simple paths admitted by polyhedra of given dimension and having a given number of facets. Section II is devoted to the conjecture that any 2 vertices of a polyhedron can be joined by a path therein which never returns to a facet from which it has departed earlier. The conjecture is proved for 3-dimensional polyhedra, and a stronger form (dealing with polyhedral cell complexes) is established for special cases.

Descriptors :   (*GEOMETRIC FORMS, LINEAR PROGRAMMING), (*LINEAR PROGRAMMING, GEOMETRIC FORMS), LINEAR PROGRAMMING, CONVEX BODIES, CONVEX SETS, COMBINATORIAL ANALYSIS, NUMERICAL ANALYSIS, GEOMETRY

Distribution Statement : APPROVED FOR PUBLIC RELEASE