Paths, cycles and related partitioning problems in graphs

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
  • Formal Methods and Tools
  • University of Twente
Supervisors/Advisors
  • Broersma, Haitze J., Supervisor
Sponsors
Date of Award1 Sep 2017
Place of PublicationEnschede
Print ISBNs978-90-365-4385-9
DOIs
StatePublished - 1 Sep 2017

Fingerprint

Path
Cycle
Extendability
Tournament
Digraph
Hamiltonicity
Partition
Graph in graph theory
Multipartite tournaments
Pancyclicity
Degree condition
Edge-colored graph
Oriented graph
Clique
Random graphs
Directed graph
Enumeration
Contraction
Partitioning
Open problems

Keywords

  • Graphs
  • Paths
  • Cycles
  • Partitioning

Cite this

@misc{65a9d97ceaf346698cdd6444b03e8981,
title = "Paths, cycles and related partitioning problems in graphs",
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.",
keywords = "Graphs, Paths, Cycles, Partitioning",
author = "Zanbo Zhang",
note = "CTIT Ph.D. thesis series no. 17-441",
year = "2017",
month = "9",
doi = "10.3990/1.9789036543859",
isbn = "978-90-365-4385-9",
school = "Formal Methods and Tools, University of Twente",

}

Paths, cycles and related partitioning problems in graphs. / Zhang, Zanbo .

Enschede, 2017. 155 p.

Research output: ScientificPhD Thesis - Research UT, graduation UT

TY - THES

T1 - Paths, cycles and related partitioning problems in graphs

AU - Zhang,Zanbo

N1 - CTIT Ph.D. thesis series no. 17-441

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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.

AB - 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.

KW - Graphs

KW - Paths

KW - Cycles

KW - Partitioning

U2 - 10.3990/1.9789036543859

DO - 10.3990/1.9789036543859

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4385-9

ER -