Graphs of Transportation Polytopes

Abstract

This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an $m\times n$ transportation polytope is a multiple of the greatest common divisor of $m$ and $n$.

29 pages, 7 figures. Final version. Improvements to the exposition of several lemmas and the upper bound in Theorem 1.1 is improved by a factor of two

Cited by in corpus (8)

• An update on the Hirsch conjecture
• Multistationarity in the space of total concentrations for systems that admit a monomial parametrization
• Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method
• Counting Integer Points in Multi-Index Transportation Polytopes
• Transportation Polytope and its Applications in Parallel Server Systems
• The Hierarchy of Circuit Diameters and Transportation Polytopes
• The Diameters of Network-flow Polytopes satisfy the Hirsch Conjecture
• On sub-determinants and the diameter of polyhedra