Varianten zur Matching Extendability in Graphen

• Some generalizations of matching extendability in graphs

Schmidt, Isabelle Gertrud; Triesch, Eberhard (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen (2019)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2019

Abstract

On the one hand a 1-matching or simply a matching of a graph G=(V,E) is a set of pairwise non incident edges. On the other hand it can be described as an edge function which maps the values 0 and 1 to the edges of G such that the sum of values of incident edges to each vertex is at most 1. A 1-matching is called perfect if the sum of incident edges in each vertex equals 1. We define the size of a 1-matching as the sum of values over all edgesWe say that a graph G is 1-matching k-extendable if every matching of size k in G extends to a perfect matching of G. The extendability number of G is the maximal integer k such that G is 1-matching k-extendable. Describing a 1-matching as an edge function yields to the more general concept of b-matchings. In analogy to the 1-matching extendability we define the b-matching extendability and the 2-matching extendability as a special case. In this thesis we study the complexity of determining the extendability number for 2- and b-matchings. After a brief survey of the theory on 1-matching extendability we present a result of hackfeld from 2013. He proved that the extendability problem is co-NP-complete for general graphs. Furthermore, we discuss a result of Zhang und Zhang showing that there is a polynomial time algorithm which computes the 1-matching extendability number of bipartite graphs. We generalize both results for 2-and b-matchings. Considering the extendability for 2-Matchings it points out that different approaches seem to be natural. Thus we introduce the concepts of simple, Typ A and Typ B 2-matching k-extendability. For these concepts we transfer a basic property of 1-matching k-extendable graphs. In particular, we show that a graph which is simple (resp. Typ A or Typ B) k-extendable is simple (resp. Typ A or Typ B) (k-1)-extendable. Moreover, we prove that for general graphs the problem of determining the simple, Typ A and Typ B 2-matching extendability number is co-NP-complete by using an analog deduction to the proof of Hackfelds result. For the Typ B 2-matching extendability we obtain the same statement from the following result on the b-matching extendability. In particular, we generalize all results of Typ B for general and bipartite graphs to the b-matching extendability. We give an (alternative) algorithm which determines the b-matching extendability number for bipartite graphs. This procedure generalizes the result of Zhang und Zhang for the 1-matching extendability number of bipartite graphs.