Journal article icon

Journal article

Hamilton cycles, minimum degree, and bipartite holes

Abstract:

We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large “bipartite hole” (two disjoint sets of vertices with no edges between them). This result extends Dirac's classical theorem, and is related to a theorem of Chvátal and Erdős. In detail, an inline image-bipartite-hole in a graph G consists of two disjoint sets of vertices S and T with inline image and inline image such that there are no edges between S and T; and in...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1002/jgt.22114

Authors


More by this author
Department:
Corpus Christi College
More by this author
Department:
Oxford, MPLS, Computer Science
Publisher:
Wiley Publisher's website
Journal:
Journal of Graph Theory Journal website
Volume:
86
Issue:
3
Pages:
277–285
Publication date:
2017-07-07
Acceptance date:
2016-11-09
DOI:
EISSN:
1097-0118
ISSN:
0364-9024
Pubs id:
pubs:707580
URN:
uri:064c62f6-c583-4cf9-9716-ef86335b9b7a
UUID:
uuid:064c62f6-c583-4cf9-9716-ef86335b9b7a
Local pid:
pubs:707580
Paper number:
3

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP