Paths, cycles and related partitioning problems in graphs

Zanbo Zhang

    Research output: ThesisPhD Thesis - Research UT, graduation UT

    134 Downloads (Pure)

    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 in-degree and out-degree 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 2-paths 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 edge-colored 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 2-paths 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 in-out 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 path-extendability and cycle-extendability, so that we can use a former result of Hendry to simplify one of our proofs.
    Original languageEnglish
    Awarding Institution
    • University of Twente
    Supervisors/Advisors
    • Broersma, Hajo, Supervisor
    Thesis sponsors
    Award date1 Sep 2017
    Place of PublicationEnschede
    Publisher
    Print ISBNs978-90-365-4385-9
    DOIs
    Publication statusPublished - 1 Sep 2017

    Keywords

    • Graphs
    • Paths
    • Cycles
    • Partitioning

    Fingerprint Dive into the research topics of 'Paths, cycles and related partitioning problems in graphs'. Together they form a unique fingerprint.

    Cite this