PhD defence Zanbo Zhang

Paths,cycles and related partitioning problems in graphs

The main theme of this thesis is centered around paths and cycles in graphs, while there is also one chapter devoted to partitioning problems that do not only involve cycles but also cliques.

A graph is a mathematical concept consisting of a set of elements, together with a set of (ordered or unordered) pairs of its elements, where the latter set of pairs is a subset of the set of all (ordered or unordered) possible pairs of its elements. This means that graphs can model a variety of practical situations in which one is faced with a set of objects, called vertices, and relationships between (some of) the pairs of these objects. If these relationships are symmetric, they are modeled by unordered pairs called edges; otherwise, they are modeled by ordered pairs called arcs.

Given a graph that models a practical situation, or given a graph just as a mathematical object, one might be interested in structural properties of the graph, or in conditions that guarantee such properties. As an example, in many applications it is important to know whether the graph that models the situation, is connected, meaning that there exist paths between every pair of its vertices. Here, with a (directed) path we mean a sequence of distinct vertices v1, v2, ..., vk and edges (arcs) vivi+1 (we usually omit the brackets and comma in the pairs that correspond to edges or arcs) betweens all successive vertices in the sequence, between the two vertices v1 and vk of the pair. So, we require connecting paths between all the pairs of vertices, not only between the pairs that are joined by an edge (arc). Similarly, a (directed) cycle is a sequence of distinct vertices v1, v2, ..., vk and edges (arcs) vivi+1 between all successive vertices in the sequence, with an additional edge (arc) vk v1.

Paths and cycles are among the most commonly studied structures in graphs, and have attracted many researchers for a relatively long time. Tracing back to 1857, Sir William Rowan Hamilton invented the Icosian Game, which involves constructing a cycle containing every vertex of the graph that represents a dodecahedron. Started in such a form as a recreational game, path and cycle problems became a hot area of research since the middle of the last century, and now form an important branch of graph theory, encompassing many challenging problems, deep results and important applications.

Named after Sir William Rowan Hamilton, a Hamiltonian path (cycle) of a graph G is a path (cycle) in G that contains every vertex of G. Correspondingly, a graph with a Hamiltonian path (cycle) is called traceable (Hamiltonian). Problems on Hamiltonian paths and cycles have many practical application, for instance in interconnection network design, in VLSI design and in DNA analysis. However, the problem of deciding whether a given graph admits a Hamiltonian path (or Hamiltonian cycle) is generally NP-complete, which means that an efficient algorithm to solve this decision problem is not likely to exist. Similarly, there exists no elegant, easy to apply set of conditions that characterize in which cases a graph is Hamiltonian. This was, and still is, one of the main motivations for the vast amount of research onHamiltonian paths and Hamiltonian cycles in graphs, trying to tackle various related problems from a computational, algorithmic or theoretical perspective.

In theoretical research, a lot of graph parameters and properties, involving the vertex degrees, the cardinalities of neighborhood sets, the number of edges, and the independence number and vertex connectivity, have been associated with traceability and Hamiltonicity. Most of the corresponding results appear in the form of sufficient conditions for the existence of Hamiltonian cycles in certain graph classes. One of the main results in this thesis improves a classical degree sum condition due to Woodall for Hamiltonicity in digraphs.

It is a common approach within graph theory to strengthen or extend existing results on the existence of certain structures, by trying to strengthen the conclusion or relax the conditions for such structures. There are several ways to generalize or extend the notion of a Hamiltonian cycle or path. One can ask for the number of Hamiltonian cycles, instead of just the existence of a Hamiltonian cycle, that is implied by a certain condition. This leads to enumeration problems, that are not a subject of this thesis. One can further require that these Hamiltonian cycles are edge-disjoint, leading to problems involving Hamiltonian cycle packings or decompositions, that are not the subject of this thesis either. In a slightly different direction, one can work on cycle factors of a graph. A cycle factor of a graph is a set of disjoint cycles, the union of which covers all the vertices of the graph. Thus, a Hamiltonian cycle is a special cycle factor consisting of only one cycle. Some sufficient conditions for Hamiltonicity, or their strengthenings, imply cycle factors with additional constraints on the number or the length of the cycles.

The main idea behind most of the results in this thesis, is to establish conditions that guarantee the existence of cycles with many different lengths in a graph. Let n denote the number of vertices of the graphs we consider, unless otherwise specified. Then, a graph containing cycles of every length from 3 to n is called pancyclic. In 1971 and 1973, Bondy defined the concept of pancyclicity in some pioneering work in this direction. There, he also raised the following meta-conjecture that has become well-known within the graph theory community.

Meta-conjecture. Almost any nontrivial condition on a graph which implies that the graph is Hamiltonian also implies that the graph is pancyclic (possibly with some exceptional graphs that can be easily characterized).

In many cases, sufficient conditions for Hamiltoncity imply that the graphs are dense (contain relatively many edges), and therefore the meta-conjecture of Bondy is likely to hold. This meta-conjecture motivated countless subsequent contributions of results on pancyclicity and other related concepts, such as panconnectedness. A graph is called panconnected, if there is a path of length k from u to v for every two distinct vertices u and v, and for every k with 3 k n−1. Hence, panconnectedness is the counterpart of pancyclicity for the existence of paths instead of cycles with many different lengths.

Later, around 1990, Hendry went further, by defining cycle extendability and path extendability. He observed that many proofs for Hamiltonicity are based on a proof by contradiction or contraposition. In such proofs, one assumes that the graph is not Hamiltonian, starts by considering a maximal non-Hamiltonian cycle C, and tries to find a longer cycle C', hence a contradiction, or a violation of the condition in the hypothesis of the result. As Hendry observed, in many cases this C' consists of all the vertices of C, and one additional vertex. This led to the notion of cycle extendability: Hendry defined the cycle C to be extendable, whenever such a cycle C' exists. The definition of path extendability is similar. A non-Hamiltonian path P of length at least one is called extendable if there exists another path P' with the same end vertices of P, whose vertex set consists of the vertex set of P and one additional vertex. A graph G is called cycle (path) extendable, if every non-Hamiltonian cycle (path of length at least 1) of G is extendable. If G is cycle extendable and has a cycle C of length 3, we can start from C, repeatedly apply the operation of extending a cycle, until we get a Hamiltonian cycle. Then, we have cycles of every length from 3 to n. In this sense, cycle extendability is a stronger property than pancyclicity, and similarly, path extendability is stronger than panconnectedness.

It is then natural to ask whether Bondy’s meta-conjecture also holds for cycle extendability and path extendability, which is one of the themes of this thesis. An interesting observation in the work of Hendry and our work in this thesis reveals that, with respect to cycle extendability and path extendability, the validity of Bondy’s meta-conjecture in undirected graphs and digraphs is different. As an example, if we consider a so-called Dirac-type degree condition for Hamiltonicity in undirected graphs, involving a lower bound on the degree of every vertex in the graph, we will find that this condition, sometimes with a slight strengthening, often implies pancyclicity, cycle extendability and even path extendability. Moreover, usually their counterparts in digraphs also imply pancyclicity. However, to guarantee cycle extendability and path extendability in digraphs, one needs to raise the lower bound on the vertex degrees significantly.

Another interesting problem in this context is, to answer the question in which classes of graphs Bondy’s meta-conjecture always holds, that is, in which classes Hamiltonicity and pancyclicity become equivalent. One can find several examples in the literature. In his well-known work on Hamiltonicity in squares of graphs, Fleischner proved that in for squares of graphs, Hamiltonicity and pancyclicity are equivalent. As another example, in tournaments, strongness has been shown to be equivalent to Hamiltonicity and pancyclicity. As before, in our studies we want to go one step further, and try to include cycle extendability into this equivalence relation. Next, we consider another example. A chordal graph is a graph in which every cycle of length at least 3 has a chord, i.e., an edge joining two vertices of the cycle that are nonadjacent on the cycle. It is easy to deduce that a chordal graph with a Hamiltonian cycle is pancyclic. Hendry raised the problem whether a Hamiltonian chordal graph is cycle extendable. This problem can be understood as a query on the equivalence between Hamiltonicity and cycle extendability in chordal graphs. For several subclasses of chordal graphs, this equivalent relation has been verified. However, the equivalence is not valid in general chordal graphs, as has been shown by Lafond and Seamone recently. For classes of digraphs, Hendry has shown that in tournaments Hamiltonicity and cycle extendability are equivalent. One of our contributions is an analogous result that verifies the equivalence of these properties in bipartite tournaments.

Next to theoretical problems and results on the existence of various path and cycle structures, a lot of closely related computational and algorithmic problems can be raised. A natural and important one for applications, is the problem of determining a cycle factor of a graph, in contrast to just proving sufficiency results for its existence. As defined above, a cycle factor of a graph G is a collection of mutually disjoint cycles of G such that each vertex of G is contained in exactly one of these cycles. We consider this cycle factor problem in edge-colored graphs, that belongs to the very broad and well-studied area of graph partitioning problems. These partitioning problems of edge-colored graphs have many applications, e.g., in graph-based data mining. In the latter field, the vertices of a graph denote the entities in a system, usually a large network, and the edges between the vertices represent relationships between the entities, with different colors denoting different kinds of relationships. According to different requirements in real-world applications or theoretical considerations, different structures are studied, e.g., cliques, cycles, paths and trees, with respect to these partitioning problems. In the final chapter of this thesis, we prove computational complexity and algorithmic results for what are called the multicolored cycle problem and the monochromatic clique problem.