Treglown, Andrew Clark
(2011).
Embedding problems in graphs and hypergraphs.
University of Birmingham.
Ph.D.
Abstract
The first part of this thesis concerns perfect matchings and their generalisations. We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph, thereby answering a question of Hàn, Person and Schacht. We say that a graph \(G\) has a perfect \(H\)-packing (also called an \(H\) - factor) if there exists a set of disjoint copies of \(H\) in \(G\) which together cover all the vertices of \(G\). Given a graph \(H\), we determine, asymptotically, the Ore-type degree condition which ensures that a graph \(G\) has a perfect \(H\)-packing. The second part of the thesis concerns Hamilton cycles in directed graphs. We give a condition on the degree sequences of a digraph \(G\) that ensures \(G\) is Hamiltonian. This gives an approximate solution to a problem of Nash-Williams concerning a digraph analogue of Chvatal's theorem. We also show that every sufficiently large regular tournament can almost completely be decomposed into edge-disjoint Hamilton cycles. More precisely, for each \(\eta\) >0 every regular tournament \(G\) of sufficiently large order n contains at least (1/2- \(\eta\))n edge-disjoint Hamilton cycles. This gives an approximate solution to a conjecture of Kelly from 1968.
Actions
 |
Request a Correction |
 |
View Item |
Downloads per month over past year