Edge-extremal graphs under degree and matching number restrictions

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Boğaziçi Üniversitesi, FEN BİLİMLERİ ENSTİTÜSÜ, FEN BİLİMLERİ ENSTİTÜSÜ, Türkiye

Tezin Onay Tarihi: 2016

Tezin Dili: İngilizce

Öğrenci: CEMİL DİBEK

Danışman: TINAZ EKİM

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

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.