Degree Conditions for Hamiltonian Properties of Claw-free Graphs

Tao Tian

    Research output: ThesisPhD Thesis - Research UT, graduation UT

    88 Downloads (Pure)

    Abstract

    This thesis contains many new contributions to the field of hamiltonian graph theory, a very active subfield of graph theory. In particular, we have obtained new sufficient minimum degree and degree sum conditions to guarantee that the graphs satisfying these conditions, or their line graphs, admit a Hamilton cycle (or a Hamilton path), unless they have a small order or they belong to well-defined classes of exceptional graphs. Here, a Hamilton cycle corresponds to traversing the vertices and edges of the graph in such a way that all their vertices are visited exactly once, and we return to our starting vertex (similarly, a Hamilton path reflects a similar way of traversing the graph, but without the last restriction, so we might terminate at a different vertex).

    In Chapter 1, we presented an introduction to the topics of this thesis together with Ryjáček’s closure for claw-free graphs, Catlin’s reduction method, and the reduction of the core of a graph. In Chapter 2, we found the best possible bounds for the minimum degree condition and the minimum degree sums condition of adjacent vertices for traceability of 2-connected claw-free graph, respectively. In addition, we decreased these lower bounds with one family of well characterized exceptional graphs. In Chapter 3, we extended recent results about the conjecture of Benhocine et al. and results about the conjecture of Z.-H Chen and H.-J Lai. In Chapters 4, 5 and 6, we have successfully tried to unify and extend several existing results involving the degree and neighborhood conditions for the hamiltonicity and traceability of 2-connected claw-free graphs.

    Throughout this thesis, we have investigated the existence of Hamilton cycles and Hamilton paths under different types of degree and neighborhood conditions, including minimum degree conditions, minimum degree sum conditions on adjacent pairs of vertices, minimum degree sum conditions over all independent sets of t vertices of a graph, minimum cardinality conditions on the neighborhood union over all independent sets of t vertices of a graph, as well minimum cardinality conditions on the neighborhood union over all t vertex sets of a graph. Despite our new contributions, many problems and conjectures remain unsolved.
    Original languageEnglish
    Awarding Institution
    Supervisors/Advisors
    • Broersma, Hajo, Supervisor
    Award date5 Sep 2019
    Place of PublicationEnschede
    Publisher
    Print ISBNs978-90-365-4610-2
    DOIs
    Publication statusPublished - 5 Sep 2018

    Fingerprint

    Degree Condition
    Claw-free Graphs
    Minimum Degree
    Degree Sum
    Hamilton Path
    Hamilton Cycle
    Graph in graph theory
    Vertex of a graph
    Traceability
    Independent Set
    Graph theory
    Connected graph
    Cardinality
    Union
    Adjacent
    Graph Reduction
    Hamiltonian Graph
    Hamiltonicity
    Line Graph
    Subfield

    Keywords

    • Degree conditions
    • Hamilton cycle
    • Hamilton path
    • Closure
    • Reduction
    • Claw-free graphs

    Cite this

    Tian, Tao . / Degree Conditions for Hamiltonian Properties of Claw-free Graphs. Enschede : Ipskamp Printing, 2018. 131 p.
    @phdthesis{47d1009282bd4a309cb04bac2daa563f,
    title = "Degree Conditions for Hamiltonian Properties of Claw-free Graphs",
    abstract = "This thesis contains many new contributions to the field of hamiltonian graph theory, a very active subfield of graph theory. In particular, we have obtained new sufficient minimum degree and degree sum conditions to guarantee that the graphs satisfying these conditions, or their line graphs, admit a Hamilton cycle (or a Hamilton path), unless they have a small order or they belong to well-defined classes of exceptional graphs. Here, a Hamilton cycle corresponds to traversing the vertices and edges of the graph in such a way that all their vertices are visited exactly once, and we return to our starting vertex (similarly, a Hamilton path reflects a similar way of traversing the graph, but without the last restriction, so we might terminate at a different vertex). In Chapter 1, we presented an introduction to the topics of this thesis together with Ryj{\'a}ček’s closure for claw-free graphs, Catlin’s reduction method, and the reduction of the core of a graph. In Chapter 2, we found the best possible bounds for the minimum degree condition and the minimum degree sums condition of adjacent vertices for traceability of 2-connected claw-free graph, respectively. In addition, we decreased these lower bounds with one family of well characterized exceptional graphs. In Chapter 3, we extended recent results about the conjecture of Benhocine et al. and results about the conjecture of Z.-H Chen and H.-J Lai. In Chapters 4, 5 and 6, we have successfully tried to unify and extend several existing results involving the degree and neighborhood conditions for the hamiltonicity and traceability of 2-connected claw-free graphs.Throughout this thesis, we have investigated the existence of Hamilton cycles and Hamilton paths under different types of degree and neighborhood conditions, including minimum degree conditions, minimum degree sum conditions on adjacent pairs of vertices, minimum degree sum conditions over all independent sets of t vertices of a graph, minimum cardinality conditions on the neighborhood union over all independent sets of t vertices of a graph, as well minimum cardinality conditions on the neighborhood union over all t vertex sets of a graph. Despite our new contributions, many problems and conjectures remain unsolved.",
    keywords = "Degree conditions, Hamilton cycle, Hamilton path, Closure, Reduction, Claw-free graphs",
    author = "Tao Tian",
    year = "2018",
    month = "9",
    day = "5",
    doi = "10.3990/1.9789036546102",
    language = "English",
    isbn = "978-90-365-4610-2",
    series = "DSI Ph.D. Thesis Series",
    publisher = "Ipskamp Printing",
    number = "18-013",
    address = "Netherlands",

    }

    Degree Conditions for Hamiltonian Properties of Claw-free Graphs. / Tian, Tao .

    Enschede : Ipskamp Printing, 2018. 131 p.

    Research output: ThesisPhD Thesis - Research UT, graduation UT

    TY - THES

    T1 - Degree Conditions for Hamiltonian Properties of Claw-free Graphs

    AU - Tian, Tao

    PY - 2018/9/5

    Y1 - 2018/9/5

    N2 - This thesis contains many new contributions to the field of hamiltonian graph theory, a very active subfield of graph theory. In particular, we have obtained new sufficient minimum degree and degree sum conditions to guarantee that the graphs satisfying these conditions, or their line graphs, admit a Hamilton cycle (or a Hamilton path), unless they have a small order or they belong to well-defined classes of exceptional graphs. Here, a Hamilton cycle corresponds to traversing the vertices and edges of the graph in such a way that all their vertices are visited exactly once, and we return to our starting vertex (similarly, a Hamilton path reflects a similar way of traversing the graph, but without the last restriction, so we might terminate at a different vertex). In Chapter 1, we presented an introduction to the topics of this thesis together with Ryjáček’s closure for claw-free graphs, Catlin’s reduction method, and the reduction of the core of a graph. In Chapter 2, we found the best possible bounds for the minimum degree condition and the minimum degree sums condition of adjacent vertices for traceability of 2-connected claw-free graph, respectively. In addition, we decreased these lower bounds with one family of well characterized exceptional graphs. In Chapter 3, we extended recent results about the conjecture of Benhocine et al. and results about the conjecture of Z.-H Chen and H.-J Lai. In Chapters 4, 5 and 6, we have successfully tried to unify and extend several existing results involving the degree and neighborhood conditions for the hamiltonicity and traceability of 2-connected claw-free graphs.Throughout this thesis, we have investigated the existence of Hamilton cycles and Hamilton paths under different types of degree and neighborhood conditions, including minimum degree conditions, minimum degree sum conditions on adjacent pairs of vertices, minimum degree sum conditions over all independent sets of t vertices of a graph, minimum cardinality conditions on the neighborhood union over all independent sets of t vertices of a graph, as well minimum cardinality conditions on the neighborhood union over all t vertex sets of a graph. Despite our new contributions, many problems and conjectures remain unsolved.

    AB - This thesis contains many new contributions to the field of hamiltonian graph theory, a very active subfield of graph theory. In particular, we have obtained new sufficient minimum degree and degree sum conditions to guarantee that the graphs satisfying these conditions, or their line graphs, admit a Hamilton cycle (or a Hamilton path), unless they have a small order or they belong to well-defined classes of exceptional graphs. Here, a Hamilton cycle corresponds to traversing the vertices and edges of the graph in such a way that all their vertices are visited exactly once, and we return to our starting vertex (similarly, a Hamilton path reflects a similar way of traversing the graph, but without the last restriction, so we might terminate at a different vertex). In Chapter 1, we presented an introduction to the topics of this thesis together with Ryjáček’s closure for claw-free graphs, Catlin’s reduction method, and the reduction of the core of a graph. In Chapter 2, we found the best possible bounds for the minimum degree condition and the minimum degree sums condition of adjacent vertices for traceability of 2-connected claw-free graph, respectively. In addition, we decreased these lower bounds with one family of well characterized exceptional graphs. In Chapter 3, we extended recent results about the conjecture of Benhocine et al. and results about the conjecture of Z.-H Chen and H.-J Lai. In Chapters 4, 5 and 6, we have successfully tried to unify and extend several existing results involving the degree and neighborhood conditions for the hamiltonicity and traceability of 2-connected claw-free graphs.Throughout this thesis, we have investigated the existence of Hamilton cycles and Hamilton paths under different types of degree and neighborhood conditions, including minimum degree conditions, minimum degree sum conditions on adjacent pairs of vertices, minimum degree sum conditions over all independent sets of t vertices of a graph, minimum cardinality conditions on the neighborhood union over all independent sets of t vertices of a graph, as well minimum cardinality conditions on the neighborhood union over all t vertex sets of a graph. Despite our new contributions, many problems and conjectures remain unsolved.

    KW - Degree conditions

    KW - Hamilton cycle

    KW - Hamilton path

    KW - Closure

    KW - Reduction

    KW - Claw-free graphs

    U2 - 10.3990/1.9789036546102

    DO - 10.3990/1.9789036546102

    M3 - PhD Thesis - Research UT, graduation UT

    SN - 978-90-365-4610-2

    T3 - DSI Ph.D. Thesis Series

    PB - Ipskamp Printing

    CY - Enschede

    ER -

    Tian T. Degree Conditions for Hamiltonian Properties of Claw-free Graphs. Enschede: Ipskamp Printing, 2018. 131 p. (DSI Ph.D. Thesis Series; 18-013). https://doi.org/10.3990/1.9789036546102