Edge-extremal graphs under degree and matching number restrictions
Maksimum derecesi ve eşleme sayısı sınırlı, kenar sayısı en çok olan çizgeler
- Tez No: 433957
- Danışmanlar: DOÇ. DR. TINAZ EKİM AŞICI
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Matematik, Industrial and Industrial Engineering, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 61
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Constructing edge extremal triangle-free graphs withbounded maximum degree and matching number using integerprogramming
Maksimum derecesi ve eşleme sayısı sınırlı, kenar sayısı en çok olan üçgen-yoksun çizgelerin tamsayılı programlama ile inşası
ALİ ERDEM BANAK
Yüksek Lisans
İngilizce
2023
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ZEKİ CANER TAŞKIN
PROF. DR. TINAZ EKİM AŞICI
- Extremal graph theory and applying the regularity lemma
Ekstrem graf teori ve regülerlik lemmasının uygulanması
ALI FAROOQ SADEQ SADEQ
Yüksek Lisans
İngilizce
2022
MatematikÇankırı Karatekin ÜniversitesiMatematik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ CELALETTİN KAYA
- Yüksek boyutlu imge özniteliklerine dayalı ilgi bölgesi tespiti
High dimensional image features based interest region detection
MESUT GÜNEY
Yüksek Lisans
Türkçe
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDeniz Harp Okulu KomutanlığıBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. NAFİZ ARICA
- Görüntü işleme yöntemleri ile yüzey üzerine oyulmuş karakterlerin tanınması
The recognition of engraving character on the surface with image processing methods
MAHMUT SAMİ YASAK
Yüksek Lisans
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. HASAN ERDİNÇ KOÇER
- Hematoksilen-eozin ve floresan ın situ hibridizasyon ile boyanan histopatoloji görüntülerinin imge çakıştırma yöntemleriyle ile eşleştirilmesi
Matching of histopathology images stained with hematoxylin-eosin and fluorescent in situ hybridization with image registration methods
ZAFER SÜNETCİ
Yüksek Lisans
Türkçe
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Medeniyet ÜniversitesiNanobilim ve Nanomühendislik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ NURULLAH ÇALIK