sufficient conditions for hamiltonian properties of graphs

*Qiannan Zhou is a PhD student in the research group Formal Methods and Tools. Her supervisors are prof.dr.ir. H.J. Broersma from the faculty of Electrical Engineering, Mathematics and Computer Science and prof.dr. L. Wang from the Northwestern Polytechnical University.*

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. The vertices and edges in the graph can respectively represent a set of objects and the existing relationships between pairs of these objects. Hence by using a graph, one can simplify a possibly complicated problem in ones daily life, by focussing on the essential information only. This makes graphs very widely applicable as mathematical abstractions in a diversity of practical settings and a huge range of scientific areas.

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 NP-complete. This is the main reason why most researchers have focussed 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 a graph to have a Hamilton cycle in terms of structural or algebraic parameters. Besides this, a large part of this thesis deals with sufficient conditions for other hamiltonian properties. The first of these other hamiltonian properties we consider is called 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 x-path, i.e., a Hamilton path starting at vertex x. So, the second other hamiltonian property we deal with is that the graph is traceable from every arbitrary vertex. The last hamiltonian property we take into account is Hamilton-connectivity, which requires that any two distinct vertices can be connected by a Hamilton path.

During the past decades, people have focused on finding sufficient or necessary conditions for hamiltonian properties from many different angles, using graph concepts such as the degree of the vertices, forbidden subgraphs, the Wiener index, the spectral radius, and so on. The results in this thesis mainly involve degree conditions, spectral conditions, and Wiener index and Harary index conditions for traceability, hamiltonicity or Hamilton-connectivity 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.