Maximal nonrevisiting paths in simple polytopes

DOI10.1016/S0012-365X(02)00525-3MaRDI QIDQ1869200zbMATH OpenOpenAlexFDO

Authors Fred B. Holt

Publication date 9 April 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00525-3

zbMATH Keywords

Hirsch conjecturenonrevisiting conjecturepathspolytopesstrong \(d\)-step conjecture

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11)

Review text

Let \(\Delta(d,n)\) denote the maximum edge-diameter among all simple \(d\)-dimensional polytopes with \(n\) facets. The Hirsch conjecture states that \(\Delta(d,n)\leq n-d\) for all \(n> d\geq 2\). The nonrevisiting path conjecture states that in any polytope, every pair of vertices is connected by a nonrevisiting path. These two conjectures have been shown to be equivalent. Recently operations on polytopes (such as wedging) have been used to get the best available results related to the Hirsch conjecture. The author uses the same operations to study the maximal number of nonrevisiting paths in simple polytopes.

Recommendations

• Paths on polymatroids
• Monotone paths on polytopes
• Optimum turn-restricted paths, nested compatibility, and optimum convex polygons
• scientific article; zbMATH DE number 4021183
• Computing monotone disjoint paths on polytopes
• On Shortest Paths in Polyhedral Spaces
• On the length of monotone paths in polyhedra
• Simple paths on polyhedra
• Disjoint paths spanning simple polytopal graphs
• Lemke Paths on Simple Polytopes

Cited in

(7)

• Non-revisiting paths on surfaces with low genus
• Hirsch polytopes with exponentially long combinatorial segments
• Nonrevisiting paths on surfaces
• On the path avoiding forbidden pairs polytope
• The Mani-Walkup Spherical Counterexamples to the W_v-Path Conjecture are Not Polytopal
• Lemke Paths on Simple Polytopes
• One-point suspensions and wreath products of polytopes and spheres

This page was built for publication: Maximal nonrevisiting paths in simple polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869200)