Cubic vertices in planar hypohamiltonian graphs. (English) Zbl 1466.05038

Zamfirescu, Carol T.

J. Graph Theory 90, No. 2, 189-207 (2019).

Summary: C. Thomassen [Discrete Math. 14, 377–389 (1976; Zbl 0322.05130)] showed that every planar hypohamiltonian graph contains a cubic vertex. Equivalently, a planar graph with minimum degree at least 4 in which every vertex-deleted subgraph is hamiltonian, must be itself hamiltonian. By applying work of G. Brinkmann and C. T. Zamfirescu [Electron. J. Comb. 26, No. 1, Research Paper P1.39, 16 p. (2019; Zbl 1409.05122)], we extend this result in three directions. We prove that (i) every planar hypohamiltonian graph contains at least four cubic vertices, (ii) every planar almost hypohamiltonian graph contains a cubic vertex, which is not the exceptional vertex (solving a problem of the author raised in [C. T. Zamfirescu, J. Graph Theory 79, No. 1, 63–81 (2015; Zbl 1312.05076)], and (iii) every hypohamiltonian graph with crossing number 1 contains a cubic vertex. Furthermore, we settle a recent question of Thomassen by proving that asymptotically the ratio of the minimum number of cubic vertices to the order of a planar hypohamiltonian graph vanishes.

MSC:

05C07	Vertex degrees
05C10	Planar graphs; geometric and topological aspects of graph theory
05C45	Eulerian and Hamiltonian graphs

Keywords:

hypohamiltonian graphs; planar graphs; 3-connected graphs; 3-cut

Citations:

Zbl 0322.05130; Zbl 1409.05122; Zbl 1312.05076