Edge - extremal graphs under degree and matching number restrictions

Abstract

A graph with an upper bound on its matching number but without a bound on its maximum degree, or a graph with an upper bound on its maximum degree but without a bound on its matching number would have in nitely many edges. In order to limit the maximum number of edges of a graph to a nite number, bounds on both maximum degree and matching number are needed. The edge-extremal problem deals with maximizing the number of edges of a graph under restrictions on its maximum degree and matching number. This type of problems are generally studied in the eld of Extremal Graph Theory whose main concern is to nd extremal graphs that satisfy a certain property. The answer to the edge-extremal problem is known for arbitrary graphs [1]. It is interesting to solve the edge-extremal problem when imposed some structure on the given graphs since the maximum number of edges may change upon narrowing the graph class. The answer when the graphs belong to some chosen graph classes is provided by a recent master thesis [2]. The problem has been answered in that thesis for bipartite graphs, split graphs, disjoint union of split graphs and unit interval graphs. It is observed that star graphs seem to play a central role in the bound on edges. Some open questions have been therefore posed concerning how allowing or disallowing stars a ects the bound on the number of edges. In this thesis we provide, to the best of our knowledge, the rst results of the edge-extremal problem in clawfree graphs. We nd an answer to the change in edge-extremal instances for general graphs when we do not allow claws, which is a special star graph. For this purpose, we develop several claw-free graph constructions and we nd the number of edges of an edge-extremal claw-free graph, not only by giving the number itself but also by providing an edge-extremal claw-free graph for each possible case.