Matchings, factors and cycles in graphs
Publication Date
2008
Creator
Abstract
A matching in a graph is a set of pairwise nonadjacent edges, a k-factor is a k-regular spanning subgraph, and a cycle is a closed path.
This thesis has two parts. In Part I (by far the larger part) we study sufficient conditions for structures involving matchings, factors and cycles. The three main types of conditions involve: the minimum degree; the degree sum of pairs of nonadjacent vertices (Ore-type conditions); and the neighbourhoods of independent sets of vertices. We show that most of our theorems are best possible by giving appropriate extremal graphs. We study Ore-type conditions for a graph to have a Hamilton cycle or 2-factor containing a given matching or path-system, and for any matching and single vertex to be contained in a cycle. We give Ore-type and neighbourhood conditions for a matching L of l edges to be contained in a matching of k edges (l < k). We generalise two different aspects of this result: the l = 0 case with an Ore-type condition for a heavy matching in an edge-weighted graph; and the conditions for a perfect matching containing L with degree and neighbourhood conditions for a k-factor (k > 2) containing a given set of edges. We also establish neighbourhood conditions for the existence of a cycle of length at least k. A list-edge-colouring of a graph is an assignment of a colour to each edge from its own list of colours. In Part II we study edge colourings of powers of cycles, and prove the List-Edge-Colouring Conjecture for squares of cycles of odd length.
This thesis has two parts. In Part I (by far the larger part) we study sufficient conditions for structures involving matchings, factors and cycles. The three main types of conditions involve: the minimum degree; the degree sum of pairs of nonadjacent vertices (Ore-type conditions); and the neighbourhoods of independent sets of vertices. We show that most of our theorems are best possible by giving appropriate extremal graphs. We study Ore-type conditions for a graph to have a Hamilton cycle or 2-factor containing a given matching or path-system, and for any matching and single vertex to be contained in a cycle. We give Ore-type and neighbourhood conditions for a matching L of l edges to be contained in a matching of k edges (l < k). We generalise two different aspects of this result: the l = 0 case with an Ore-type condition for a heavy matching in an edge-weighted graph; and the conditions for a perfect matching containing L with degree and neighbourhood conditions for a k-factor (k > 2) containing a given set of edges. We also establish neighbourhood conditions for the existence of a cycle of length at least k. A list-edge-colouring of a graph is an assignment of a colour to each edge from its own list of colours. In Part II we study edge colourings of powers of cycles, and prove the List-Edge-Colouring Conjecture for squares of cycles of odd length.
Item Type
ethesis
Thesis Type
PhD
Supervisors
Subjects (LC)
Associated Schools / Departments
School of Mathematical Sciences (UK)
eprints ID
10530
UoN Repository URI
Except where otherwise noted, this item's license is described as
File(s)![Thumbnail Image]()
Name
finalthesis.pdf
Type
Full-text
Size
649.35 KB
Format
Adobe PDF
Checksum ()