Path-matchings Of Graphs

As a common generalization of matchings and matroid intersection, Cunningham and Geelen introduced the notion of path-matchings in 1996. They showed that problems in many fields can be transformed into path-matching problems. In other words, by using path-matchings many problems in matchings, matroid, polyhedron and algebra can be solved. As the applications of path-matchings, they developed a strongly polynomial separation algorithm for the matchable set polyhedron, and proved that the maximum value of a path-matching is the rank of vertices set in the matching matroid determined by some given graph, and is also equal to the rank of an Tutte matrix, etc.This thesis consists of six chapters. In the first Chapter, we introduce the background of application on path-matchings and the important papers in this area since the notion of path-matchings was introduced. Then we summarize the main results of this thesis. In Chapter 2 and 3, we describe structure of graphs by using maximum path-matchings. In the last three chapters, we consider the size of maximum path-matchings and the extensibility of perfect path-matchings in a given graphIn 2004, Spille and Szego gave a similar decomposition {A₁, C₁, D₁} on vertex-set of some graph with Gallai-Edmonds decomposition {A, C, D} under the sense of matchings, and presented the corresponding structure theorem for path-matchings. We have known that the intersection of all maximal barriers is equal to set A. In Chapter 2, we give a generalization of this result to the framework of path-matchings and get an expression on A₁.In Gallai-Edmonds structure theorem, each component of graph induced by D is factor-critical (that is, the deletion of any vertex results in a perfectly matchable graph). The characterization of such graphs has been obtained in matching theory. While the graphs induced by D₁ in the corresponding path-matching vertices decomposition are not always factor-critical. Therefor, we characterize the graphs induced by D₁ and discuss the relationship between two kinds of components in such graphs.Frank and Szego presented a characterization theorem of graphs with perfect path-matchings which generalizes the Tutte's theorem. While as a sufficient condition of a graph with perfect path-matchings it is so strong. Thus in Chapter 4 we mainly consider the existence of perfect path-matchings in general graphs and some special graphs. For general graphs, we present extreme set condition and binding-number-type conditions for a graph to have a perfect path-matching. Further we show these binding-number-type conditions are best possible in some sense. Some sufficient conditions for the existence of perfect path-matching of regular graphs and K_1,t-free graphs are presented.The path-matching number val(G) of a graph G = (V,T₁,T₂;E) is a parameter of describing the size of maximum path-matchings in G. In Chapter 5, val(G) is bounded by two different ways. More precisely, the first bound is given by a certain function on binding number b, |V|, and |T_i|, where i = 1,2,. which generalizes the Woodall's result on matching number. The second, which is considered in K_1,t-free graphs, is given by a functions on t, the connectivity m, |V|, and |T_i|.In Chapter 4, we have discussed the existence of a perfect path-matching. Then a question appears: can we extend any proper path-matching with value n to a perfect path-matching by strengthen the conditions in these theorems? In the last Chapter, we present the definition of n-extendable on path-matchings. It is just a generalization of the matching extensibility. We give sufficient conditions for n-extendable graphs on binding-number-type when |V| and n + k have the same parity or k > n, where k is the size of terminal set in graph G, and show that the conditions can not be weakened in some sense. As an immediate consequence, we improve the result presented by Chen on matching extensibility of graphs. Then in the case of |V| and n + k having different parity and k≤n, we show that there is no direct relationship between extensibility on path-matchings and the binding number. Finally, sufficient conditions for path-matching extensibility on K_1,t-free graphs are given.