Paths and Cycles in Digraphs

ISBN-13: 9783659184284 / Angielski / Miękka / 2012 / 76 str.

Saddam Zaid

Opis

This book is intended to investigate a famous conjecture in Graph Theory proposed by Caccetta and Haggkvist in 1978. The book demonstrates the conjecture which has two forms, and the equivalence of the two forms of the conjecture is proven. The conjecture relates the outdegree of the vertices in a digraph along with the existence of a short directed cycle of certain length in that digraph. Here, two main approaches to resolve the conjecture will be described. The first approach is by Hamidoune to prove the conjecture if the outdegree of each vertex in the digraph is at most three. The second approach is by Hoang and Reed to prove the conjecture if the outdegree of each vertex in the digraph is at most five. Both these approaches are investigated in detail and new techniques are developed in order to be used for subsequent research. Occasionally, the techniques used to prove the conjecture if the outdegree of each vertex is five can also be used to prove the conjecture if the outdegree of each vertex is six.

O autorze

Zaid, SaddamSaddam Zaid has obtained his Master degree in Theoretical Mathematics in 2011. Since then he has worked as an instructor in BZU teaching both Theoretical and Applied Mathematics to students in Mathematics, Engineering, Commerce, and Social Sciences. His main research interest is in Graph Theory, Combinatorics, Matrix Theory, and Algebraic Topology.