On cycles in directed graphs

Kelly, Luke Tristian (2010). On cycles in directed graphs. University of Birmingham. Ph.D.

[img]
Preview
kelly_10_PhD.pdf
PDF

Download (2MB)

Abstract

The main results of this thesis are the following. We show that for each alpha > 0 every sufficiently large oriented graph G with minimum indegree and minimum outdegree at least 3 |G| / 8 + alpha |G| contains a Hamilton cycle. This gives an approximate solution to a problem of Thomassen. Furthermore, answering completely a conjecture of Haggkvist and Thomason, we show that we get every possible orientation of a Hamilton cycle. We also deal extensively with short cycles, showing that for each l > 4 every sufficiently large oriented graph G with minimum indegree and minimum outdegree at least |G| / 3 + 1 contains an l-cycle. This is best possible for all those l > 3 which are not divisible by 3. Surprisingly, for some other values of l, an l-cycle is forced by a much weaker minimum degree condition. We propose and discuss a conjecture regarding the precise minimum degree which forces an l-cycle (with l > 3 divisible by 3) in an oriented graph. We also give an application of our results to pancyclicity.

Type of Work: Thesis (Doctorates > Ph.D.)
Award Type: Doctorates > Ph.D.
Supervisor(s):
Supervisor(s)EmailORCID
Osthus, DerykUNSPECIFIEDUNSPECIFIED
Kuhn, DanielaUNSPECIFIEDUNSPECIFIED
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/940

Actions

Request a Correction Request a Correction
View Item View Item

Downloads

Downloads per month over past year