Sufficient conditions for hamiltonian properties of graphs

Qiannan Zhou

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

11 Downloads (Pure)

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 NP-complete. 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 x-path, 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 Hamilton-connectivity, 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 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.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Hajo, Supervisor
  • Wang, Ligong, Co-Supervisor
Award date10 Oct 2019
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-4864-9
DOIs
Publication statusPublished - 2019

Fingerprint

Sufficient Conditions
Graph in graph theory
Hamilton Path
Hamilton Cycle
Vertex of a graph
Traceability
Connectivity
Distinct
Degree Condition
Hamiltonicity
Wiener Index
Path
Unordered
Graph theory
Join
NP-complete problem
Cycle
Subset
Arbitrary

Cite this

Zhou, Qiannan . / Sufficient conditions for hamiltonian properties of graphs. Enschede : University of Twente, 2019. 161 p.
@phdthesis{1c818cd3e43a45708f9001ab4754e4f5,
title = "Sufficient conditions for hamiltonian properties of graphs",
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 NP-complete. 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 x-path, 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 Hamilton-connectivity, 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 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.",
author = "Qiannan Zhou",
year = "2019",
doi = "10.3990/1.9789036548649",
language = "English",
isbn = "978-90-365-4864-9",
series = "DSI Ph.D. thesis series",
publisher = "University of Twente",
number = "19-017",
address = "Netherlands",
school = "University of Twente",

}

Zhou, Q 2019, 'Sufficient conditions for hamiltonian properties of graphs', Doctor of Philosophy, University of Twente, Enschede. https://doi.org/10.3990/1.9789036548649

Sufficient conditions for hamiltonian properties of graphs. / Zhou, Qiannan .

Enschede : University of Twente, 2019. 161 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

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 NP-complete. 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 x-path, 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 Hamilton-connectivity, 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 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.

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 NP-complete. 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 x-path, 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 Hamilton-connectivity, 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 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.

U2 - 10.3990/1.9789036548649

DO - 10.3990/1.9789036548649

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4864-9

T3 - DSI Ph.D. thesis series

PB - University of Twente

CY - Enschede

ER -

Zhou Q. Sufficient conditions for hamiltonian properties of graphs. Enschede: University of Twente, 2019. 161 p. (DSI Ph.D. thesis series; 19-017). https://doi.org/10.3990/1.9789036548649