Back to search

University of Birmingham

Packings and coverings with Hamilton cycles and on-line Ramsey theory

Abstract

dc:description.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 edge-disjoint Hamilton cycles. • Let \(T\) be a strongly k-connected tournament. We give an almost tight lower bound on the size of a maximal packing of \(T\) with edge-disjoint Hamilton cycles. • Let log 117 \(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 on-line Ramsey theory. Let r(\(G\),\(H\)) denote the on-line 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 ℓ.

Degree

thesis:*
Name dc:type.qualificationname
d_ph
Level dc:type.qualificationlevel
d_ph
Grantor dc:publisher.institution
University of Birmingham
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lapinskas, John Adam

Subjects

dc:subject × 1

Rights

Language dc:language.dcterms_iso639_2
eng

Chain of custody

source
Harvested from
University of Birmingham
Base URL
etheses.bham.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lapinskas, John Adam. Packings and coverings with Hamilton cycles and on-line Ramsey theory. d_ph thesis, University of Birmingham, 2014.