Online citations, reference lists, and bibliographies.
← Back to Search

Cubic Vertices In Planar Hypohamiltonian Graphs

C. Zamfirescu
Published 2019 · Mathematics, Computer Science

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Share
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Get Citationsy
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
Polyeder und Raumeinteilungen
E. Steinitz (1922)
10.1007/978-1-4612-2972-8_4
Congruent Graphs and the Connectivity of Graphs
H. Whitney (1932)
Quelques conséquences simples de la formule d’Euler
H. Lebesgue (1940)
10.1090/S0002-9947-1956-0081471-8
A THEOREM ON PLANAR GRAPHS
W. T. Tutte (1956)
Recherche systématique des graphes hypohamiltoniens
J. C. Herz (1967)
Problem 4
T. Gallai (1968)
10.4153/CMB-1973-008-9
Flip-flops in hypo-Hamiltonian graphs
V. Chvátal (1973)
10.1016/0097-3165(74)90025-9
Vertices Missed by Longest Paths or Circuits
B. Grünbaum (1974)
10.7146/MATH.SCAND.A-11630
On longest paths and circuits in graphs.
T. Zamfirescu (1976)
10.1016/0012-365X(76)90071-6
Planar and infinite hypohamiltonian and hypotraceable graphs
Carsten Thomassen (1976)
10.1002/net.3230080303
Systematic searches for hypohamiltonian graphs
J. Collier (1978)
10.1007/BFB0070410
Hypohamiltonian graphs and digraphs
Carsten Thomassen (1978)
10.1016/0095-8956(81)90089-7
Planar cubic hypohamiltonian and hypotraceable graphs
C. Thomassen (1981)
10.1002/jgt.3190070205
A theorem on paths in planar graphs
Carsten Thomassen (1983)
10.1017/cbo9780511662058.002
The Petersen graph
D. Holton (1993)
10.1006/jctb.1994.1058
4-Connected Projective-Planar Graphs Are Hamiltonian
R. Thomas (1994)
10.1137/S0895480198348665
Nonhamiltonian 3-Connected Cubic Planar Graphs
R. Aldred (2000)
10.1016/S0012-365X(03)00317-0
A successful concept for measuring non-planarity of graphs: the crossing number
L. Székely (2004)
10.1002/JGT.V55:4
A planar hypohamiltonian graph with 48 vertices
C. Zamfirescu (2007)
10.37236/572
On Cubic Planar Hypohamiltonian and Hypotraceable Graphs
M. Araya (2011)
10.1002/JGT.20513
On planar hypohamiltonian graphs
Gábor Wiener (2011)
10.1007/s00373-012-1165-z
An Infinite Family of Planar Hypohamiltonian Oriented Graphs
S. V. Aardt (2013)
10.1016/j.jctb.2013.05.001
Generation and properties of snarks
G. Brinkmann (2013)
10.5614/ejgta.2013.1.1.6
Intersecting longest paths and longest cycles: A survey
Ayesha Shabbir (2013)
10.1016/j.ejc.2013.06.033
2-edge-Hamiltonian-connectedness of 4-connected plane graphs
K. Ozeki (2014)
10.1007/s00373-013-1312-1
Infinite families of 2-hypohamiltonian/2-hypotraceable oriented graphs
S. V. Aardt (2014)
10.1002/jgt.21815
On Hypohamiltonian and Almost Hypohamiltonian Graphs
C. Zamfirescu (2015)
10.1016/j.endm.2015.07.034
Hypohamiltonian Snarks Have a 5-Flow
Breno Lima de Freitas (2015)
10.26493/1855-3974.1044.eaa
Improved bounds for hypohamiltonian graphs
Jan Goedgebeur (2017)
10.1002/jgt.22034
Leaf-Critical and Leaf-Stable Graphs
G. Wiener (2017)
10.1002/jgt.22015
Planar Hypohamiltonian Graphs on 40 Vertices
Mohammadreza Jooyandeh (2017)
10.1002/jgt.22043
Hypohamiltonian Planar Cubic Graphs with Girth 5
B. McKay (2017)
P
M. Jooyandeh (2017)
10.1002/jgt.22173
New constructions of hypohamiltonian and hypotraceable graphs
G. Wiener (2018)
10.1002/jgt.22228
Every graph occurs as an induced subgraph of some hypohamiltonian graph
C. Zamfirescu (2018)
10.37236/7771
Polyhedra with Few 3-Cuts are Hamiltonian
G. Brinkmann (2019)



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