Abstract
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.
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 Dive into the research topics of 'Sufficient conditions for hamiltonian properties of graphs'. Together they form a unique fingerprint.
Cite this
Zhou, Q. (2019). Sufficient conditions for hamiltonian properties of graphs. Enschede: University of Twente. https://doi.org/10.3990/1.9789036548649