Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs

Wei Zheng

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

12 Downloads (Pure)

Abstract

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 well-known NP-complete 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 hamiltonian-connectedness, 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 languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Hajo, Supervisor
  • Wang, Ligong, Supervisor
Award date11 Jul 2019
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-4808-3
DOIs
Publication statusPublished - 2019

Fingerprint

Toughness
Subgraph
Graph in graph theory
Hamilton Cycle
Graph theory
Sufficient Conditions
Cycle
Hamilton Path
Pancyclicity
Distinct
Path
Unordered
Sufficiency
Connectedness
Vertex of a graph
Decision problem
Join
Computational Complexity
NP-complete problem

Cite this

Zheng, Wei . / Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs. Enschede : University of Twente, 2019. 149 p.
@phdthesis{2e148efdd5424b4c921a29a30525c598,
title = "Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs",
abstract = "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 well-known NP-complete 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 hamiltonian-connectedness, 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.",
author = "Wei Zheng",
year = "2019",
doi = "10.3990/1.9789036548083",
language = "English",
isbn = "978-90-365-4808-3",
series = "DSI Ph.D. thesis series",
publisher = "University of Twente",
number = "19-012",
address = "Netherlands",
school = "University of Twente",

}

Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs. / Zheng, Wei .

Enschede : University of Twente, 2019. 149 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

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 well-known NP-complete 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 hamiltonian-connectedness, 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 well-known NP-complete 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 hamiltonian-connectedness, 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 - 978-90-365-4808-3

T3 - DSI Ph.D. thesis series

PB - University of Twente

CY - Enschede

ER -

Zheng W. Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs. Enschede: University of Twente, 2019. 149 p. (DSI Ph.D. thesis series; 19-012). https://doi.org/10.3990/1.9789036548083