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 Oretype degree conditions are known since the 1960s. These Oreconditions 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 Oretype 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 Oretype 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 language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  20 Sep 2012 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036534031 
DOIs  
Publication status  Published  20 Sep 2012 
Keywords
 EWI23935
 MSC05C45
 METIS288149
 Hamilton path
 (Hamilton) cycle
 Forbidden subgraph
 Graph Theory
 IR81499
Cite this
Li, B., & Li, B. (2012). Subgraph conditions for Hamiltonian properties of graphs. Enschede: Universiteit Twente. https://doi.org/10.3990/1.9789036534031