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

Hypohamiltonian Graphs And Digraphs

C. Thomassen
Published 1978 · Mathematics

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
Methods for constructing hypohamiltonian graphs and oriented graphs are described. It is shown that every planar hypohamiltonian graph contains a vertex of degree 3 and that for each n ≥ 6 there exists a planar, hypohamiltonian digraph with n vertices. Finally it is proved that every graph with n vertices contains a set A of at most 1/3n vertices such that every longest cycle of the graph intersects A.
This paper references



This paper is referenced by
A pr 2 02 1 Polyhedra without cubic vertices are prism-hamiltonian
Simon Špacapan (2021)
Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs
C. Zamfirescu (2021)
K2-hamiltonian graphs: I
C. Zamfirescu (2021)
10.1002/JGT.22672
On 3-polytopes with non-Hamiltonian prisms
Daiki Ikegami (2021)
4-regular 4-connected Hamiltonian graphs with few Hamiltonian cycles
C. Thomassen (2021)
Polyhedra without cubic vertices are prism-hamiltonian
Simon vSpacapan (2021)
Regular graphs with few longest cycles
C. Zamfirescu (2021)
4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles
C. Thomassen (2021)
10.1016/j.amc.2020.125714
Non-hamiltonian graphs in which every edge-contracted subgraph is hamiltonian
Igor Fabrici (2021)
Sublinear Longest Path Transversals and Gallai Families
James A. Long (2020)
10.1016/j.amc.2020.125491
Structural and computational results on platypus graphs
Jan Goedgebeur (2020)
10.26493/1855-3974.1291.ee9
On the size of maximally non-hamiltonian digraphs
N. Lichiardopol (2019)
10.1007/s00373-019-02010-9
On a Question of van Aardt et al. on Destroying All Longest Cycles
C. Zamfirescu (2019)
10.23638/DMTCS-21-4-5
On almost hypohamiltonian graphs
Jan Goedgebeur (2019)
10.1002/jgt.22714
Transversals of Longest Cycles in Partial k-Trees and Chordal Graphs
J. Guti'errez (2019)
10.1002/jgt.22388
Cubic vertices in planar hypohamiltonian graphs
C. Zamfirescu (2019)
10.1016/j.dam.2018.02.017
Gallai's question and constructions of almost hypotraceable graphs
Gábor Wiener (2018)
10.7494/OPMATH.2018.38.3.357
Forbidden configurations for hypohamiltonian graphs
Igor Fabrici (2018)
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.1137/17M1138443
Every 4-Connected Graph with Crossing Number 2 is Hamiltonian
K. Ozeki (2018)
10.1007/978-3-319-77404-6_41
Transversals of Longest Cycles in Chordal and Bounded Tree-Width Graphs
J. Gutiérrez (2018)
10.11606/t.45.2020.tde-10012020-200714
Transversals of graphs
Juan Gabriel Gutierrez Alva (2018)
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.23638/DMTCS-19-1-4
The Existence of Planar Hypotraceable Oriented Graphs
S. V. Aardt (2017)
10.1002/jgt.22015
Planar Hypohamiltonian Graphs on 40 Vertices
Mohammadreza Jooyandeh (2017)
10.1002/jgt.22122
On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable
C. Zamfirescu (2017)
10.1007/978-3-319-28186-5_21
Seven Problems on Hypohamiltonian and Almost Hypohamiltonian Graphs
C. Zamfirescu (2016)
New results on hypohamiltonian and almost hypohamiltonian graphs
Jan Goedgebeur (2016)
10.1007/s00373-015-1561-2
Hypohamiltonian Oriented Graphs of All Possible Orders
S. V. Aardt (2015)
10.1002/jgt.21815
On Hypohamiltonian and Almost Hypohamiltonian Graphs
C. Zamfirescu (2015)
See more
Semantic Scholar Logo Some data provided by SemanticScholar