Edge-extremal graphs under degree and matching number restrictions

Abstract

Eşleme sayısı üstten sınırlı fakat maksimum derecesi sınırlı olmayan bir çizgenin ya da maksimum derecesi üstten sınırlı fakat eşleme sayısı sınırlı olmayan bir çizgenin sonsuz sayıda kenarı olabilir. Bir çizgenin maksimum kenar sayısının sonlu bir sayı olabilmesi için hem maksimum derecesi hem de eşleme sayısının üstten sınırlanması gerekir. Uç kenar problemi, maksimum derecesi ve eşleme sayısı sınırlı bir çizgenin kenar sayısını maksimize etmek ile ilgilenir. Bu tip problemler genelde, ana konusu belli özellikleri sağlayan uç çizgeleri bulmak olan Uç Çizge Teorisi alanında çalışılır. Uç kenar probleminin çözümü genel çizgeler sınıfı için bilinmektedir. Uç kenar problemini, çizgelere belli yapısal özellikler eklendiğinde çözmeye çalışmak ilginçtir çünkü maksimum kenar sayısı çizge sınıfı daraltıldığında değişebilir.Çizgeler seçilen bir çizge sınıfına ait iken uç kenar probleminin çözümü yakın zamanda yapılmış bir yüksek lisans tezinde sunulmuştur. Orada problem, bipartit çizgeler, split çizgeler, split çizgelerin ayrık birleşimi ve birim aralık çizgeler sınıfları için çözülmüştür. Yıldız çizgelerin, kenar sayısındaki sınırlarda çok önemli bir rol oynadığı görülmüştür. Bu sebeple, yıldız çizgelere izin verip vermemenin kenar sayısını nasıl etkileyeceğiyle ilgili bazı açık sorular sorulmuştur. Bu tezde, uç kenar probleminin pençesiz çizgelerdeki ilk sonuçlarını sunuyoruz.Özel bir yıldız çizge olan pençeye izin verilmediğinde uç kenar probleminin genel çizgelerdeki sonucunun nasıl değiştiğine bir cevap buluyoruz. Bu amaçla, birkaç pençesiz çizge yapısı geliştiriyoruz ve kenar sayısı en çok olan pençesiz çizgelerin kenar sayısını buluyoruz. Sadece sayıyı vermekle kalmıyor, aynı zamanda her olası durum için kenar sayısı en çok olan pençesiz çizgeler sunuyoruz.

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 infinitely many edges. In order to limit the maximum number of edges of a graph to a finite 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 field of Extremal Graph Theory whose main concern is to find extremal graphs that satisfy a certain property. The answer to the edge-extremal problem is known for arbitrary graphs. 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. 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 affects the bound on the number of edges. In this thesis we provide, to the best of our knowledge, the first results of the edge-extremal problem in claw-free graphs. We find 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 find 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.