Back to search

University of Birmingham

Substructures in large graphs

Abstract

dc:description.abstract

The first problem we address concerns Hamilton cycles. Suppose G is a large digraph in which every vertex has in- and outdegree at least |G|/2. We show that G contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla. Our result is best possible and improves on an approximate result by Häggkvist and Thomason. We then investigate the random greedy F-free process which was initially studied by Erdős, Suen and Winkler and by Spencer. This process greedily adds edges without creating a copy of F, terminating in a maximal F-free graph. We provide an upper bound on the number of hyperedges at the end of this process for a large class of hypergraphs. The remainder of this thesis focuses on F-decompositions, i.e., whether the edge set of a graph can be partitioned into copies of F. We obtain the best known bounds on the minimum degree which ensures a Kr-decomposition of an r-partite graph, with applications to Latin squares. Lastly, we find exact bounds on the minimum degree for a large graph to have a C2k-decomposition where k≠3. In both cases, we assume necessary divisibility conditions are satisfied.

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
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Taylor, Amelia May

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

Taylor, Amelia May. Substructures in large graphs. d_ph thesis, University of Birmingham, 2017.