Subgraph conditions for Hamiltonian properties of graphs

Binlong Li, Binlong Li

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

81 Downloads (Pure)

Abstract

The research that forms the basis of this thesis addresses the following general structural questions in graph theory: which fixed graph of pair of graphs do we have to forbid as an induced subgraph of an arbitrary graph G to guarantee that G has a nice structure? In this thesis the nice structural property we have been aiming for is the existence of a Hamilton cycle, i.e., a cycle containing all the vertices of the graph, or related properties like the existence of a Hamilton path, of cycles of every length, or of Hamilton paths starting at every vertex of the graph. For these structural properties, sufficient Ore-type degree conditions are known since the 1960s. These Ore-conditions are of the type: if every pair of nonadjacent vertices of the graph G has degree sum at least some lower bound, the G is guaranteed to have the structural property. In order to obtain common generalizations of these sufficiency results based on Ore-type degree sum conditions on one hand and forbidden induced subgraph conditions on the other hand, the following questions have also been addressed in the thesis. Can we restrict the corresponding Ore-type degree sum condition to certain induced subgraphs of pairs of induced subgraphs of a graph G and still guarantee that G has the same nice structure? In the thesis work we have proved many examples that provide affirmative answers to these general questions. We refer to the listed chapters for the details and the the precise definitions and formulations of the results.
Original languageUndefined
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Hajo, Supervisor
  • Broersma, H.J., Supervisor
  • Zhang, S., Supervisor
Thesis sponsors
Award date20 Sep 2012
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-3403-1
DOIs
Publication statusPublished - 20 Sep 2012

Keywords

  • EWI-23935
  • MSC-05C45
  • METIS-288149
  • Hamilton path
  • (Hamilton) cycle
  • Forbidden subgraph
  • Graph Theory
  • IR-81499

Cite this

Li, Binlong ; Li, Binlong. / Subgraph conditions for Hamiltonian properties of graphs. Enschede : Universiteit Twente, 2012. 221 p.
@phdthesis{add966c5cd2a45c2869873849b41ec62,
title = "Subgraph conditions for Hamiltonian properties of graphs",
abstract = "The research that forms the basis of this thesis addresses the following general structural questions in graph theory: which fixed graph of pair of graphs do we have to forbid as an induced subgraph of an arbitrary graph G to guarantee that G has a nice structure? In this thesis the nice structural property we have been aiming for is the existence of a Hamilton cycle, i.e., a cycle containing all the vertices of the graph, or related properties like the existence of a Hamilton path, of cycles of every length, or of Hamilton paths starting at every vertex of the graph. For these structural properties, sufficient Ore-type degree conditions are known since the 1960s. These Ore-conditions are of the type: if every pair of nonadjacent vertices of the graph G has degree sum at least some lower bound, the G is guaranteed to have the structural property. In order to obtain common generalizations of these sufficiency results based on Ore-type degree sum conditions on one hand and forbidden induced subgraph conditions on the other hand, the following questions have also been addressed in the thesis. Can we restrict the corresponding Ore-type degree sum condition to certain induced subgraphs of pairs of induced subgraphs of a graph G and still guarantee that G has the same nice structure? In the thesis work we have proved many examples that provide affirmative answers to these general questions. We refer to the listed chapters for the details and the the precise definitions and formulations of the results.",
keywords = "EWI-23935, MSC-05C45, METIS-288149, Hamilton path, (Hamilton) cycle, Forbidden subgraph, Graph Theory, IR-81499",
author = "Binlong Li and Binlong Li",
year = "2012",
month = "9",
day = "20",
doi = "10.3990/1.9789036534031",
language = "Undefined",
isbn = "978-90-365-3403-1",
publisher = "Universiteit Twente",
school = "University of Twente",

}

Subgraph conditions for Hamiltonian properties of graphs. / Li, Binlong; Li, Binlong.

Enschede : Universiteit Twente, 2012. 221 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - Subgraph conditions for Hamiltonian properties of graphs

AU - Li, Binlong

AU - Li, Binlong

PY - 2012/9/20

Y1 - 2012/9/20

N2 - The research that forms the basis of this thesis addresses the following general structural questions in graph theory: which fixed graph of pair of graphs do we have to forbid as an induced subgraph of an arbitrary graph G to guarantee that G has a nice structure? In this thesis the nice structural property we have been aiming for is the existence of a Hamilton cycle, i.e., a cycle containing all the vertices of the graph, or related properties like the existence of a Hamilton path, of cycles of every length, or of Hamilton paths starting at every vertex of the graph. For these structural properties, sufficient Ore-type degree conditions are known since the 1960s. These Ore-conditions are of the type: if every pair of nonadjacent vertices of the graph G has degree sum at least some lower bound, the G is guaranteed to have the structural property. In order to obtain common generalizations of these sufficiency results based on Ore-type degree sum conditions on one hand and forbidden induced subgraph conditions on the other hand, the following questions have also been addressed in the thesis. Can we restrict the corresponding Ore-type degree sum condition to certain induced subgraphs of pairs of induced subgraphs of a graph G and still guarantee that G has the same nice structure? In the thesis work we have proved many examples that provide affirmative answers to these general questions. We refer to the listed chapters for the details and the the precise definitions and formulations of the results.

AB - The research that forms the basis of this thesis addresses the following general structural questions in graph theory: which fixed graph of pair of graphs do we have to forbid as an induced subgraph of an arbitrary graph G to guarantee that G has a nice structure? In this thesis the nice structural property we have been aiming for is the existence of a Hamilton cycle, i.e., a cycle containing all the vertices of the graph, or related properties like the existence of a Hamilton path, of cycles of every length, or of Hamilton paths starting at every vertex of the graph. For these structural properties, sufficient Ore-type degree conditions are known since the 1960s. These Ore-conditions are of the type: if every pair of nonadjacent vertices of the graph G has degree sum at least some lower bound, the G is guaranteed to have the structural property. In order to obtain common generalizations of these sufficiency results based on Ore-type degree sum conditions on one hand and forbidden induced subgraph conditions on the other hand, the following questions have also been addressed in the thesis. Can we restrict the corresponding Ore-type degree sum condition to certain induced subgraphs of pairs of induced subgraphs of a graph G and still guarantee that G has the same nice structure? In the thesis work we have proved many examples that provide affirmative answers to these general questions. We refer to the listed chapters for the details and the the precise definitions and formulations of the results.

KW - EWI-23935

KW - MSC-05C45

KW - METIS-288149

KW - Hamilton path

KW - (Hamilton) cycle

KW - Forbidden subgraph

KW - Graph Theory

KW - IR-81499

U2 - 10.3990/1.9789036534031

DO - 10.3990/1.9789036534031

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-3403-1

PB - Universiteit Twente

CY - Enschede

ER -