Subgraph conditions for Hamiltonian properties of graphs

Binlong Li

Research output: ThesisPhD Thesis - Research UT, graduation UT

151 Downloads (Pure)

Abstract

The research that forms the basis of this thesis addresses the following general structural questions in graph theory: which fixed graph of pair of graphs do we have to forbid as an induced subgraph of an arbitrary graph G to guarantee that G has a nice structure? In this thesis the nice structural property we have been aiming for is the existence of a Hamilton cycle, i.e., a cycle containing all the vertices of the graph, or related properties like the existence of a Hamilton path, of cycles of every length, or of Hamilton paths starting at every vertex of the graph. For these structural properties, sufficient Ore-type degree conditions are known since the 1960s. These Ore-conditions are of the type: if every pair of nonadjacent vertices of the graph G has degree sum at least some lower bound, the G is guaranteed to have the structural property. In order to obtain common generalizations of these sufficiency results based on Ore-type degree sum conditions on one hand and forbidden induced subgraph conditions on the other hand, the following questions have also been addressed in the thesis. Can we restrict the corresponding Ore-type degree sum condition to certain induced subgraphs of pairs of induced subgraphs of a graph G and still guarantee that G has the same nice structure? In the thesis work we have proved many examples that provide affirmative answers to these general questions. We refer to the listed chapters for the details and the the precise definitions and formulations of the results.
Original languageEnglish
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Hajo, Supervisor
  • Zhang, Shenggui, Supervisor, External person
Thesis sponsors
Award date20 Sept 2012
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-3403-1
DOIs
Publication statusPublished - 20 Sept 2012

Keywords

  • MSC-05C45
  • Hamilton path
  • (Hamilton) cycle
  • Forbidden subgraph
  • Graph Theory

Fingerprint

Dive into the research topics of 'Subgraph conditions for Hamiltonian properties of graphs'. Together they form a unique fingerprint.

Cite this