Article in press
Authors:
Title:
On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-11-29 , Revised: 2023-08-09 , Accepted: 2023-08-09 , Available online: 2023-09-10 , https://doi.org/10.7151/dmgt.2514
Abstract:
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
References:
- G. Brinkmann and B.D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007) 323–357.
- 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 - 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 - 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 - 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 - 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 - 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 - D.A. Nelson, Hamiltonian Graphs, Master's Thesis (Vanderbilt University, 1973).
- N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences (2023).
https://oeis.org - 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 - 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 - 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 - C.T. Zamfirescu, Cubic vertices in planar hypohamiltonian graphs, J. Graph Theory 90 (2019) 189–207.
https://doi.org/10.1002/jgt.22388 - 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 - 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
Close