eTheses Repository

On cycles in directed graphs

Kelly, Luke Tristian (2010)
Ph.D. thesis, University of Birmingham.

Loading
PDF (1997Kb)

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:Ph.D. thesis.
Supervisor(s):Osthus, Deryk and Kuhn, Daniela
School/Faculty:Colleges (2008 onwards) > College of Engineering & Physical Sciences
Department:School of Mathematics
Subjects:QA Mathematics
Institution:University of Birmingham
ID Code:940
This unpublished thesis/dissertation is copyright of the author and/or third parties. The intellectual property rights of the author or third parties in respect of this work are as defined by The Copyright Designs and Patents Act 1988 or as modified by any successor legislation. Any use made of information contained in this thesis/dissertation must be in accordance with that legislation and must be properly acknowledged. Further distribution or reproduction in any format is prohibited without the permission of the copyright holder.
Export Reference As : ASCII + BibTeX + Dublin Core + EndNote + HTML + METS + MODS + OpenURL Object + Reference Manager + Refer + RefWorks
Share this item :
QR Code for this page

Repository Staff Only: item control page