Graph packing problems

Abstract

The problem of covering the vertices of a given undirected graph with a maximum number of disjoint copies of the complete graph on two vertices, K₂, is called the maximum matching problem. Due to the fruitful results of matching theory. such as the polynomial algorithms for finding the maximum matching of a given graph. it was hypothesized that similar results might hold for the analogous problem using a graph other than K₂. The problem of covering a graph with copies of graphs other than only K₂ is called the graph packing problem. Let [special characters omitted] be a family of graphs. Formally, a [special characters omitted]-packing of a graph H is a set of vertex disjoint subgraphs {G₁,…, G_k} of H such that each G_i is isomorphic to some graph in [special characters omitted]. The graph packing problem has been studied for a variety of families [special characters omitted]. Although the positive results are not as abundant as for the matching problem, many polynomial results have been found for graph packing problems on undirected graphs.

The undirected graph packing problem has now been studied quite extensively. However. this is not the case for the directed packing problem. In this thesis, we study the directed graph packing problem for families of directed paths. directed cycles and directed stars. The main new result of the thesis is a Berge-like characterization of maximum packings for the directed graph packing problem with the family {[special characters omitted]}.