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 language | English |
---|---|
Awarding Institution |
|
Supervisors/Advisors |
|
Thesis sponsors | |
Award date | 20 Sept 2012 |
Place of Publication | Enschede |
Publisher | |
Print ISBNs | 978-90-365-3403-1 |
DOIs | |
Publication status | Published - 20 Sept 2012 |
Keywords
- MSC-05C45
- Hamilton path
- (Hamilton) cycle
- Forbidden subgraph
- Graph Theory