Degree, Toughness and Subgraph Conditions for Hamiltonian Properties of Graphs

Wei Zheng

    Research output: ThesisPhD Thesis - Research UT, graduation UT

    25 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 UT

    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