Geodesic
On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1631-1646

Voir la notice de l'article provenant de la source Library of Science

Thomassen proved in 1978 that if in an n-vertex planar graph G whose minimum degree is at least 4, all vertex-deleted subgraphs of G are hamiltonian, then G is hamiltonian. It was recently shown that in the preceding sentence, “all” can be replaced by “at least n - 5”. In this note we prove that, even if 3-connectedness is assumed, it cannot be replaced by n - 24 (or any other integer greater than 24). The exact threshold remains unknown. We show that the same conclusion holds for triangulations and use computational means to prove that, under a natural restriction, this result is best possible.
Keywords: non-hamiltonian, vertex-deleted subgraph, polyhedron, planar triangulation, computation 
@article{DMGT_2024_44_4_a21,
     author = {Goedgebeur, Jan and Gringore, Thomas and Zamfirescu, Carol},
     title = {On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1631--1646},
     publisher = {mathdoc},
     volume = {44},
     number = {4},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a21/}
}
TY  - JOUR
AU  - Goedgebeur, Jan
AU  - Gringore, Thomas
AU  - Zamfirescu, Carol
TI  - On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1631
EP  - 1646
VL  - 44
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a21/
LA  - en
ID  - DMGT_2024_44_4_a21
ER  - 
%0 Journal Article
%A Goedgebeur, Jan
%A Gringore, Thomas
%A Zamfirescu, Carol
%T On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1631-1646
%V 44
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a21/
%G en
%F DMGT_2024_44_4_a21
Goedgebeur, Jan; Gringore, Thomas; Zamfirescu, Carol. On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1631-1646. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a21/