Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

Edge - extremal graphs under degree and matching number restrictions

Basit öğe kaydını göster

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Ekim, Tınaz.
dc.contributor.author Dibek, Cemil.
dc.date.accessioned 2023-03-16T10:29:03Z
dc.date.available 2023-03-16T10:29:03Z
dc.date.issued 2016.
dc.identifier.other IE 2016 D53
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13357
dc.description.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.
dc.format.extent 30 cm.
dc.publisher Thesis (M.S.)-Bogazici University. Institute for Graduate Studies in Science and Engineering, 2016.
dc.subject.lcsh Matching theory.
dc.title Edge - extremal graphs under degree and matching number restrictions
dc.format.pages x,51 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım