Abstract
The Hamilton problem, which is the problem of determining whether an arbitrarily given graph admits a Hamilton cycle (a cycle containing all the vertices of the graph), is one of the most wellknown NPcomplete decision problems within graph theory and computational complexity. People have approached this problem from many different angles, but no one has come up with an easy criterium in terms of a necessary and sufficient condition yet. Most of the research work related to this Hamilton problem is centred around finding sufficient conditions for a graph to be hamiltonian, i.e., to admit a Hamilton cycle. The main part of this thesis deals with sufficient conditions that guarantee that a graph admits a Hamilton cycle. In the other parts, we focus on related sufficient conditions for graph properties that are stronger than the property of having a Hamilton cycle, and are commonly known as hamiltonian properties. One of the stronger hamiltonian properties we consider in this thesis is called hamiltonianconnectedness, and requires that every pair of distinct vertices of the graph is connected by a Hamilton path, i.e., a path passing through each vertex of the graph exactly once. Another stronger hamiltonian property called pancyclicity requires that the graph contains cycles of any length from 3 up to the number of vertices.
The graph theoretical concepts of degree, subgraph and toughness are three commonly used concepts in studying conditions for hamiltonian properties. In this thesis, we give diverse sufficiency results in terms of these concepts by imposing certain restrictions on the degrees, subgraphs or toughness in order to guarantee the existence of certain cycles or paths. Some of our results improved the existing results, and some are new appearance in the research of graph theory.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  11 Jul 2019 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036548083 
DOIs  
Publication status  Published  2019 
Fingerprint
Cite this
}
Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs. / Zheng, Wei .
Enschede : University of Twente, 2019. 149 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs
AU  Zheng, Wei
PY  2019
Y1  2019
N2  We study graph theory. A graph is composed by a vertex set and an edge set, and each edge joins an unordered pair of (not necessarily distinct) vertices. A graph can represent any set of objects together with the existing relationships between pairs of these objects. This makes graphs very widely applicable as mathematical abstractions in a diversity of practical settings and a huge range of scientific areas. The Hamilton problem, which is the problem of determining whether an arbitrarily given graph admits a Hamilton cycle (a cycle containing all the vertices of the graph), is one of the most wellknown NPcomplete decision problems within graph theory and computational complexity. People have approached this problem from many different angles, but no one has come up with an easy criterium in terms of a necessary and sufficient condition yet. Most of the research work related to this Hamilton problem is centred around finding sufficient conditions for a graph to be hamiltonian, i.e., to admit a Hamilton cycle. The main part of this thesis deals with sufficient conditions that guarantee that a graph admits a Hamilton cycle. In the other parts, we focus on related sufficient conditions for graph properties that are stronger than the property of having a Hamilton cycle, and are commonly known as hamiltonian properties. One of the stronger hamiltonian properties we consider in this thesis is called hamiltonianconnectedness, and requires that every pair of distinct vertices of the graph is connected by a Hamilton path, i.e., a path passing through each vertex of the graph exactly once. Another stronger hamiltonian property called pancyclicity requires that the graph contains cycles of any length from 3 up to the number of vertices. The graph theoretical concepts of degree, subgraph and toughness are three commonly used concepts in studying conditions for hamiltonian properties. In this thesis, we give diverse sufficiency results in terms of these concepts by imposing certain restrictions on the degrees, subgraphs or toughness in order to guarantee the existence of certain cycles or paths. Some of our results improved the existing results, and some are new appearance in the research of graph theory.
AB  We study graph theory. A graph is composed by a vertex set and an edge set, and each edge joins an unordered pair of (not necessarily distinct) vertices. A graph can represent any set of objects together with the existing relationships between pairs of these objects. This makes graphs very widely applicable as mathematical abstractions in a diversity of practical settings and a huge range of scientific areas. The Hamilton problem, which is the problem of determining whether an arbitrarily given graph admits a Hamilton cycle (a cycle containing all the vertices of the graph), is one of the most wellknown NPcomplete decision problems within graph theory and computational complexity. People have approached this problem from many different angles, but no one has come up with an easy criterium in terms of a necessary and sufficient condition yet. Most of the research work related to this Hamilton problem is centred around finding sufficient conditions for a graph to be hamiltonian, i.e., to admit a Hamilton cycle. The main part of this thesis deals with sufficient conditions that guarantee that a graph admits a Hamilton cycle. In the other parts, we focus on related sufficient conditions for graph properties that are stronger than the property of having a Hamilton cycle, and are commonly known as hamiltonian properties. One of the stronger hamiltonian properties we consider in this thesis is called hamiltonianconnectedness, and requires that every pair of distinct vertices of the graph is connected by a Hamilton path, i.e., a path passing through each vertex of the graph exactly once. Another stronger hamiltonian property called pancyclicity requires that the graph contains cycles of any length from 3 up to the number of vertices. The graph theoretical concepts of degree, subgraph and toughness are three commonly used concepts in studying conditions for hamiltonian properties. In this thesis, we give diverse sufficiency results in terms of these concepts by imposing certain restrictions on the degrees, subgraphs or toughness in order to guarantee the existence of certain cycles or paths. Some of our results improved the existing results, and some are new appearance in the research of graph theory.
U2  10.3990/1.9789036548083
DO  10.3990/1.9789036548083
M3  PhD Thesis  Research UT, graduation UT
SN  9789036548083
T3  DSI Ph.D. thesis series
PB  University of Twente
CY  Enschede
ER 