Abstract
In this thesis we contribute with new theoretical results and algorithms to the research area related to cycles and paths in (directed) graphs.
In Chapter 2, we improve a classical result of Woodall for Hamiltonicity in digraphs, involving the sum of the indegree and outdegree of two vertices for which there is no arc from one to another, by characterizing the exceptional digraphs for the weakened condition.
In Chapter 3, we introduce and study the concept of path extendability in digraphs. Several degree and extremal conditions for path extendability are presented, and path extendability of regular tournaments is settled. Some open problems are raised.
In Chapter 4, we study cycle extendability in bipartite tournaments. We prove that in bipartite tournaments, Hamiltonicity, pancyclicity and cycle extendability are equivalent properties, with only one exceptional class that can be clearly described. We propose problems for further consideration involving the equivalence of these properties in the more general class of multipartite tournaments.
In Chapter 5, we calculate the number of 2paths between every vertex pair, a concept that one often encounters in conditions for cycle and path properties, in random oriented graphs and random tournaments. Based on our enumeration, we obtain several results related to path extendability in tournaments.
In Chapter 6, we study computational problems in the context of cycle partitions and clique partitions of edgecolored graphs, which can be viewed as a generalization of digraphs. The results of this chapter deal with computational complexity and algorithmic aspects.
Some new methods and tools are developed. In Chapter 5, the number of 2paths is used in conditions or as a tool for establishing properties related to cycles and paths in tournaments. In Chapter 4, we define the concept of the inout graph of a digraph, which is used to construct and analyze the structure of cycle factors of two intersecting cycles. To establish a degree condition for path extendability in Chapter 3, we introduce a contraction operation to relate pathextendability and cycleextendability, so that we can use a former result of Hendry to simplify one of our proofs.
In Chapter 2, we improve a classical result of Woodall for Hamiltonicity in digraphs, involving the sum of the indegree and outdegree of two vertices for which there is no arc from one to another, by characterizing the exceptional digraphs for the weakened condition.
In Chapter 3, we introduce and study the concept of path extendability in digraphs. Several degree and extremal conditions for path extendability are presented, and path extendability of regular tournaments is settled. Some open problems are raised.
In Chapter 4, we study cycle extendability in bipartite tournaments. We prove that in bipartite tournaments, Hamiltonicity, pancyclicity and cycle extendability are equivalent properties, with only one exceptional class that can be clearly described. We propose problems for further consideration involving the equivalence of these properties in the more general class of multipartite tournaments.
In Chapter 5, we calculate the number of 2paths between every vertex pair, a concept that one often encounters in conditions for cycle and path properties, in random oriented graphs and random tournaments. Based on our enumeration, we obtain several results related to path extendability in tournaments.
In Chapter 6, we study computational problems in the context of cycle partitions and clique partitions of edgecolored graphs, which can be viewed as a generalization of digraphs. The results of this chapter deal with computational complexity and algorithmic aspects.
Some new methods and tools are developed. In Chapter 5, the number of 2paths is used in conditions or as a tool for establishing properties related to cycles and paths in tournaments. In Chapter 4, we define the concept of the inout graph of a digraph, which is used to construct and analyze the structure of cycle factors of two intersecting cycles. To establish a degree condition for path extendability in Chapter 3, we introduce a contraction operation to relate pathextendability and cycleextendability, so that we can use a former result of Hendry to simplify one of our proofs.
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  1 Sep 2017 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036543859 
DOIs  
Publication status  Published  1 Sep 2017 
Keywords
 Graphs
 Paths
 Cycles
 Partitioning