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 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2024},
     volume = {44},
     number = {4},
     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
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
%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/

[1] G. Brinkmann and B.D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007) 323–357.

[2] K. Coolsaet, S. D'hondt and J. Goedgebeur, House of Graphs 2.0: A database of interesting graphs and more, Discrete Appl. Math. 325 (2023) 97–107. https://doi.org/10.1016/j.dam.2022.10.013

[3] I. Fabrici, T. Madaras, M. Timková, N. Van Cleemput and C.T. Zamfirescu, Non-hamiltonian graphs in which every edge-contracted subgraph is hamiltonian, Appl. Math. Comput. 392 (2021) 125714. https://doi.org/10.1016/j.amc.2020.125714

[4] J. Goedgebeur, B. Meersman and C.T. Zamfirescu, Graphs with few hamiltonian cycles, Math. Comp. 89 (2020) 965–991. https://doi.org/10.1090/mcom/3465

[5] J. Goedgebeur, A. Neyt and C.T. Zamfirescu, Structural and computational results on platypus graphs, Appl. Math. Comput. 386 (2020) 125491. https://doi.org/10.1016/j.amc.2020.125491

[6] B. Grünbaum, Vertices missed by longest paths or circuits, J. Combin. Theory Ser. A 17 (1974) 31–38. https://doi.org/10.1016/0097-3165(74)90025-9

[7] D.A. Holton and J. Sheehan, The Petersen Graph, Chapter 7: Hypohamiltonian graphs (Cambridge University Press, New York, 1993). https://doi.org/10.1017/CBO9780511662058.008

[8] D.A. Nelson, Hamiltonian Graphs, Master's Thesis (Vanderbilt University, 1973).

[9] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences (2023). https://oeis.org

[10] C. Thomassen, Hypohamiltonian graphs and digraphs, in: Theory and Aplications of Graphs, Lecture Notes in Math. 642, Y. Alavi and D.R. Lick (Ed(s)), (Springer, Berlin, Heidelberg 1978) 557–571. https://doi.org/10.1007/BFb0070410

[11] C. Thomassen, Planar cubic hypohamiltonian and hypotraceable graphs, J. Combin. Theory Ser. B 30 (1981) 36–44. https://doi.org/10.1016/0095-8956(81)90089-7

[12] W.T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99–116. https://doi.org/10.1090/S0002-9947-1956-0081471-8

[13] C.T. Zamfirescu, Cubic vertices in planar hypohamiltonian graphs, J. Graph Theory 90 (2019) 189–207. https://doi.org/10.1002/jgt.22388

[14] C.T. Zamfirescu, Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs, Inform. Process. Lett. 174 (2022) 106192. https://doi.org/10.1016/j.ipl.2021.106192

[15] C.T. Zamfirescu, On the hamiltonicity of a planar graph and its vertex-deleted subgraphs, J. Graph Theory 102 (2023) 180–193. https://doi.org/10.1002/jgt.22864