scientific article; zbMATH DE number 3843793
[For the entire collection see Zbl 0521.00010.] The author shows that each simple 3-polytope with at most 30 vertices is Hamiltonian. The proof works by generating a certain subfamily of these polytopes and checking its members for Hamiltonian circuits by computer. It is based on two theorems about forbidden subgraphs in an eventual counterexample with minimum number of vertices. The first one is obvious, the second one was originally proved (in a more general form) by \textit{J. W. Butler} [Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 135-151 (1975; Zbl 0332.05113)]. \textit{H. Okamura} has shown that all simple 3- polytopes with up to 32 vertices are Hamiltonian [J. Graph Theory 6, 185- 196 (1982; Zbl 0493.05043)]. His proof does not use a computer.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3313897)