Abstract
In this thesis, we focus on giving sufficient conditions for hamiltonian properties of a graph in terms of structural or algebraic parameters. Besides the Hamilton cycle, we also consider traceability. It requires that there exists a Hamilton path in the graph, i.e., a path through the vertices and edges of the graph that visits all the vertices exactly once (and does not return to the starting vertex). We say a graph is traceable if it contains a Hamilton path, and traceable from a vertex x if it contains a Hamilton xpath, i.e., a Hamilton path starting at vertex x. So, the next hamiltonian property we deal with is that the graph is traceable from every arbitrary vertex. The last hamiltonian property we take into account is Hamiltonconnectivity, which requires that any two distinct vertices can be connected by a Hamilton path.
The results in this thesis mainly involve degree conditions, spectral conditions, and Wiener index and Harary index conditions for traceability, hamiltonicity or Hamiltonconnectivity of graphs. All of our results involve the characterization of the exceptional graphs, i.e., all the nonhamiltonian graphs that satisfy the condition. Our contributions extend existing results.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  10 Oct 2019 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036548649 
DOIs  
Publication status  Published  2019 
Fingerprint
Cite this
}
Sufficient conditions for hamiltonian properties of graphs. / Zhou, Qiannan .
Enschede : University of Twente, 2019. 161 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Sufficient conditions for hamiltonian properties of graphs
AU  Zhou, Qiannan
PY  2019
Y1  2019
N2  We study graph theory. The graphs we consider in the thesis consist of a finite vertex set and a finite edge set, and each edge joins an unordered pair of (not necessarily distinct) vertices. In a graph, a round trip which visits a subset of the vertices once, is called a cycle. If such a round trip passes through every vertex of the graph precisely once, we call it a Hamilton cycle. The Hamilton problem, which is the problem of determining whether a Hamilton cycle exists in a given graph has been proved to be NPcomplete. So most researchers are focussing on establishing sufficient conditions, i.e., conditions on the graph that guarantee the existence of a Hamilton cycle.In this thesis, we focus on giving sufficient conditions for hamiltonian properties of a graph in terms of structural or algebraic parameters. Besides the Hamilton cycle, we also consider traceability. It requires that there exists a Hamilton path in the graph, i.e., a path through the vertices and edges of the graph that visits all the vertices exactly once (and does not return to the starting vertex). We say a graph is traceable if it contains a Hamilton path, and traceable from a vertex x if it contains a Hamilton xpath, i.e., a Hamilton path starting at vertex x. So, the next hamiltonian property we deal with is that the graph is traceable from every arbitrary vertex. The last hamiltonian property we take into account is Hamiltonconnectivity, which requires that any two distinct vertices can be connected by a Hamilton path.The results in this thesis mainly involve degree conditions, spectral conditions, and Wiener index and Harary index conditions for traceability, hamiltonicity or Hamiltonconnectivity of graphs. All of our results involve the characterization of the exceptional graphs, i.e., all the nonhamiltonian graphs that satisfy the condition. Our contributions extend existing results.
AB  We study graph theory. The graphs we consider in the thesis consist of a finite vertex set and a finite edge set, and each edge joins an unordered pair of (not necessarily distinct) vertices. In a graph, a round trip which visits a subset of the vertices once, is called a cycle. If such a round trip passes through every vertex of the graph precisely once, we call it a Hamilton cycle. The Hamilton problem, which is the problem of determining whether a Hamilton cycle exists in a given graph has been proved to be NPcomplete. So most researchers are focussing on establishing sufficient conditions, i.e., conditions on the graph that guarantee the existence of a Hamilton cycle.In this thesis, we focus on giving sufficient conditions for hamiltonian properties of a graph in terms of structural or algebraic parameters. Besides the Hamilton cycle, we also consider traceability. It requires that there exists a Hamilton path in the graph, i.e., a path through the vertices and edges of the graph that visits all the vertices exactly once (and does not return to the starting vertex). We say a graph is traceable if it contains a Hamilton path, and traceable from a vertex x if it contains a Hamilton xpath, i.e., a Hamilton path starting at vertex x. So, the next hamiltonian property we deal with is that the graph is traceable from every arbitrary vertex. The last hamiltonian property we take into account is Hamiltonconnectivity, which requires that any two distinct vertices can be connected by a Hamilton path.The results in this thesis mainly involve degree conditions, spectral conditions, and Wiener index and Harary index conditions for traceability, hamiltonicity or Hamiltonconnectivity of graphs. All of our results involve the characterization of the exceptional graphs, i.e., all the nonhamiltonian graphs that satisfy the condition. Our contributions extend existing results.
U2  10.3990/1.9789036548649
DO  10.3990/1.9789036548649
M3  PhD Thesis  Research UT, graduation UT
SN  9789036548649
T3  DSI Ph.D. thesis series
PB  University of Twente
CY  Enschede
ER 