×

zbMATH — the first resource for mathematics

Non-Hamiltonian simple 3-polytopes with only one type of face besides triangles. (English) Zbl 0571.05033
Convexity and graph theory, Proc. Conf., Israel 1981, Ann. Discrete Math. 20, 241-251 (1984).
[For the entire collection see Zbl 0549.00001.]
Various authors [see for instance H. Walther, Discrete Math. 33, 107-111 (1981; Zbl 0476.05051)] have studied the Hamiltonicity of simple 3-polytopes (i.e. 3-connected cubic planar graphs) with faces of only two different valencies, p and q. Here it is shown that if \(p=3\) and \(q=8\), 9 or 10, not all such 3-polytopes are Hamiltonian, and in fact the shortness coefficient of the graphs concerned is less than 1. Still open are the cases \((p,q)=(3,7),(4,7),(5,6)\) and (4,2k) for \(k\geq 4\).
Reviewer: N.Wormald

MSC:
05C45 Eulerian and Hamiltonian graphs