Degree Conditions for Hamiltonian Properties of Claw-free Graphs

Tao Tian

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

74 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 UTAcademic

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