Geri Dön

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

  1. Tez No: 433957
  2. Yazar: CEMİL DİBEK
  3. Danışmanlar: DOÇ. DR. TINAZ EKİM AŞICI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Matematik, Industrial and Industrial Engineering, Mathematics
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2016
  8. Dil: İngilizce
  9. Üniversite: Boğaziçi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2023

    Endüstri ve Endüstri MühendisliğiBoğaziçi Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. ZEKİ CANER TAŞKIN

    PROF. DR. TINAZ EKİM AŞICI

  2. 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

    İngilizce

    2022

    MatematikÇankırı Karatekin Üniversitesi

    Matematik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ CELALETTİN KAYA

  3. 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

    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

  4. 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

    Türkçe

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. HASAN ERDİNÇ KOÇER

  5. 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

    Türkçe

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Medeniyet Üniversitesi

    Nanobilim ve Nanomühendislik Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ NURULLAH ÇALIK