Abstract
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
}
Subgraph conditions for Hamiltonian properties of graphs. / Li, Binlong; Li, Binlong.
Enschede : Universiteit Twente, 2012. 221 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Subgraph conditions for Hamiltonian properties of graphs
AU  Li, Binlong
AU  Li, Binlong
PY  2012/9/20
Y1  2012/9/20
N2  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.
AB  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.
KW  EWI23935
KW  MSC05C45
KW  METIS288149
KW  Hamilton path
KW  (Hamilton) cycle
KW  Forbidden subgraph
KW  Graph Theory
KW  IR81499
U2  10.3990/1.9789036534031
DO  10.3990/1.9789036534031
M3  PhD Thesis  Research UT, graduation UT
SN  9789036534031
PB  Universiteit Twente
CY  Enschede
ER 