Online citations, reference lists, and bibliographies.

Cubic Vertices In Planar Hypohamiltonian Graphs

Carol T. Zamfirescu
Published 2019 · Mathematics, Computer Science
Cite This
Download PDF
Analyze on Scholarcy
Share
Thomassen showed in 1978 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 Brinkmann and the author, 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 J. Graph Theory [79 (2015) 63–81]), 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.
This paper references
10.1002/jgt.3190070205
A theorem on paths in planar graphs
Carsten Thomassen (1983)
10.1016/j.endm.2015.07.034
Hypohamiltonian Snarks Have a 5-Flow
Breno Lima de Freitas (2015)
10.37236/572
On Cubic Planar Hypohamiltonian and Hypotraceable Graphs
Makoto Araya (2011)
10.1002/jgt.21815
On Hypohamiltonian and Almost Hypohamiltonian Graphs
Carol T. Zamfirescu (2015)
10.4153/cmb-1973-008-9
Flip-flops in hypo-Hamiltonian graphs
Václav Chvátal (1973)
10.1016/j.ejc.2013.06.033
2-edge-Hamiltonian-connectedness of 4-connected plane graphs
Kenta Ozeki (2014)
Quelques conséquences simples de la formule d’Euler
H. Lebesgue (1940)
10.7146/math.scand.a-11630
On longest paths and circuits in graphs.
Tudor Zamfirescu (1976)
10.1002/jgt.22034
Leaf-Critical and Leaf-Stable Graphs
Gábor Wiener (2017)
10.1002/jgt.22173
New constructions of hypohamiltonian and hypotraceable graphs
Gábor Wiener (2018)
Recherche systématique des graphes hypohamiltoniens
J. C. Herz (1967)
Problem 4
T. Gallai (1968)
10.1007/s00373-013-1312-1
Infinite families of 2-hypohamiltonian/2-hypotraceable oriented graphs
Susan A. van Aardt (2014)
10.1002/jgt.22015
Planar Hypohamiltonian Graphs on 40 Vertices
Mohammadreza Jooyandeh (2017)
10.1002/jgt.22043
Hypohamiltonian Planar Cubic Graphs with Girth 5
Brendan D. McKay (2017)
10.1016/b978-0-12-384931-1.00016-7
P
J. M. Lackie (2013)
10.1007/978-1-4612-2972-8_4
Congruent Graphs and the Connectivity of Graphs
Hassler Whitney
10.1002/jgt.v55:4
A planar hypohamiltonian graph with 48 vertices
Carol T. Zamfirescu (2007)
10.1137/S0895480198348665
Nonhamiltonian 3-Connected Cubic Planar Graphs
Robert E. L. Aldred (2000)
10.1017/cbo9780511662058.002
The Petersen graph
Derek A. Holton (1993)
10.1016/j.jctb.2013.05.001
Generation and properties of snarks
Gunnar Brinkmann (2013)
10.1090/S0002-9947-1956-0081471-8
A THEOREM ON PLANAR GRAPHS
W. T. Tutte (1956)
10.37236/7771
Polyhedra with Few 3-Cuts are Hamiltonian
Gunnar Brinkmann (2018)
10.1006/jctb.1994.1058
4-Connected Projective-Planar Graphs Are Hamiltonian
Robin Thomas (1994)
10.26493/1855-3974.1044.eaa
Improved bounds for hypohamiltonian graphs
Jan Goedgebeur (2017)
10.1016/0095-8956(81)90089-7
Planar cubic hypohamiltonian and hypotraceable graphs
Carsten Thomassen (1981)
10.1007/BFb0070410
Hypohamiltonian graphs and digraphs
Carsten Thomassen (1978)
10.1016/S0012-365X(03)00317-0
A successful concept for measuring non-planarity of graphs: the crossing number
László A. Székely (2004)
10.5614/ejgta.2013.1.1.6
Intersecting longest paths and longest cycles: A survey
Ayesha Shabbir (2013)
10.1002/jgt.22228
Every graph occurs as an induced subgraph of some hypohamiltonian graph
Carol T. Zamfirescu (2018)
10.1002/net.3230080303
Systematic searches for hypohamiltonian graphs
J. B. Collier (1978)
10.1007/s00373-012-1165-z
An Infinite Family of Planar Hypohamiltonian Oriented Graphs
Susan A. van Aardt (2013)
10.1016/0012-365X(76)90071-6
Planar and infinite hypohamiltonian and hypotraceable graphs
Carsten Thomassen (1976)
10.1002/jgt.20513
On planar hypohamiltonian graphs
Gábor Wiener (2011)
10.1016/0097-3165(74)90025-9
Vertices Missed by Longest Paths or Circuits
Branko Grünbaum (1974)
Polyeder und Raumeinteilungen
E. Steinitz (1922)



This paper is referenced by
Semantic Scholar Logo Some data provided by SemanticScholar