Lapinskas, John Adam (2014). Packings and coverings with Hamilton cycles and online Ramsey theory. University of Birmingham. Ph.D.

Lapinskas14PhD.pdf
PDF  Accepted Version Download (1MB) 
Abstract
A major theme in modern graph theory is the exploration of maximal packings and minimal covers of graphs with subgraphs in some given family. We focus on packings and coverings with Hamilton cycles, and prove the following results in the area.
• Let ε > 0, and let \(G\) be a large graph on n vertices with minimum degree at least (1=2+ ε)n. We give a tight lower bound on the size of a maximal packing of \(G\) with edgedisjoint Hamilton cycles.
• Let \(T\) be a strongly kconnected tournament. We give an almost tight lower bound on the size of a maximal packing of \(T\) with edgedisjoint Hamilton cycles.
• Let log \(^1\)\(^1\)\(^7\) \(n\)/\(n\)≤\(p\)≤1\(n\)\(^\)\(^1\)\(^/\)\(^8\). We prove that \(G\)\(_n\)\(_,\)\(_p\) may a.a.s be covered by a set of ⌈Δ(\(G\)\(_n\)\(_,\)\(_p\))/2⌉ Hamilton cycles, which is clearly best possible.
In addition, we consider some problems in online Ramsey theory. Let r(\(G\),\(H\)) denote the online Ramsey number of \(G\) and \(H\). We conjecture the exact values of r (\(P\)\(_k\),\(P\)\(_ℓ\)) for all \(k\)≤ℓ. We prove this conjecture for \(k\)=2, prove it to within an additive error of 10 for \(k\)=3, and prove an asymptotically tight lower bound for \(k\)=4. We also determine r(\(P\)\(_3\),\(C\)\(_ℓ\) exactly for all ℓ.
Type of Work:  Thesis (Doctorates > Ph.D.)  

Award Type:  Doctorates > Ph.D.  
Supervisor(s): 


Licence:  
College/Faculty:  Colleges (2008 onwards) > College of Engineering & Physical Sciences  
School or Department:  School of Mathematics  
Funders:  None/not applicable  
Subjects:  Q Science > QA Mathematics  
URI:  http://etheses.bham.ac.uk/id/eprint/5453 
Actions
Request a Correction  
View Item 
Downloads
Downloads per month over past year