On the hamiltonicity of a planar graph and its vertex-deleted subgraphs |
| |
Authors: | Carol T. Zamfirescu |
| |
Affiliation: | Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Ghent, Belgium |
| |
Abstract: | Tutte proved that every planar 4-connected graph is hamiltonian. Thomassen showed that the same conclusion holds for the superclass of planar graphs with minimum degree at least 4 in which all vertex-deleted subgraphs are hamiltonian. We here prove that if in a planar -vertex graph with minimum degree at least 4 at least vertex-deleted subgraphs are hamiltonian, then the graph contains two hamiltonian cycles, but that for every there exists a nonhamiltonian polyhedral -vertex graph with minimum degree at least 4 containing hamiltonian vertex-deleted subgraphs. Furthermore, we study the hamiltonicity of planar triangulations and their vertex-deleted subgraphs as well as Bondy's meta-conjecture, and prove that a polyhedral graph with minimum degree at least 4 in which all vertex-deleted subgraphs are traceable, must itself be traceable. |
| |
Keywords: | 1-hamiltonian hamiltonian hypohamiltonian planar traceable vertex-deleted subgraph |
|
|