Pancyclic properties of the graph of some 0–1 polyhedra

AbstractIn this paper it is shown that a certain class of (0–1) polyhedra, which includes the matroid basis polytopes and the perfect matching polytopes, have graphs with the property that the edges, under a certain condition, belong to cycles of every length l ≥ 3, and the others to cycles of every length l ≥ 4. This generalizes a result of J. A. Bondy (Discrete Math. 1 (1971), 121–138) for matroids basis polytopes. It is also shown that not all (0–1) polytopes have this property even if restricted to monotone (or lower comprehensive) polytopes