Geri Dön

New structural aspects of domination and independence in graph theory

Çizge kuramında baskınlık ve bağımsızlığın yeni yapısal yönleri

  1. Tez No: 689342
  2. Yazar: HADI ALIZADEH
  3. Danışmanlar: DOÇ. DR. DİDEM GÖZÜPEK KOCAMAN
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: İngilizce
  9. Üniversite: Gebze Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 94

Özet

Baskınlık ve bağımsızlık, çizge kuramının bilgisayar bilimlerinde birçok uygulaması bulunan iki ilişkili kavramıdır. Bu tezde genel olarak baskınlık ve bağımsızlıkla ilgili problemleri ele alıyoruz. Bu bağlamda, neredeyse iyi baskınlanmış çizgeler ve eşli baskınlık konularını özel olarak ele aldık. Neredeyse iyi-baskınlanmış çizgeleri minimal baskın kümelerinin büyüklüklerinin sadece iki farklı değer alabildiği ve en büyük ile en küçük arasındaki farkın bir olduğu çizgeler olarak tanımlıyoruz. Bu tezde 3, 4, 5, ve 7 boyunda endüklenmiş döngüler içermeyen neredyse iyi-baskınlanmış çizgeler için yapısal bir karakterizasyon sunuyoruz. Daha sonra iki parçalı neredeyse iyi-baskınlanmış çizgelerle devam edip ilk önce k≥1 olmak üzere baskınlık farkı k ve minimum derecesi en az iki olan iki parçalı neredeyse iyi-baskınlanmış çizgelerin düğüm sayısı için bir üst sınır buluyoruz. Ayrıca, minimum derecesi iki olan iki-parçalı neredyse iyi-baskınlanmış çizgeler için bir yapısal karakterizasyon elde ediyoruz. Bu tez kapsamında ilgilendiğimiz bir diğer konu ise eşli baskınlıktır. Bu bağlamda özellikle Γ(G) ile gösterilen üst baskınlık sayısı ve Γ_pr (G) ile simgelenen üst eşli baskınlık sayısı olarak ifade edilen iki çizge parametresini ele alıyoruz. Sözü geçen iki çizge parametresi arasında her G çizgesi için Γ_pr (G)≤2Γ(G) şeklinde bir ilişki olduğunu ispatlıyoruz. Başlangıçta, Γ_pr (G)=2Γ(G) özelliğine sahip iki parçalı ve tek döngülü çizgeleri karakterize ederek bu tür çizgelerin yapılarını belirliyoruz. Ek olarak, Γ_pr (G)=2Γ(G) özelliğine sahip çizgelerle ilgili başka karakterizasyon sonuçları sunuyoruz. Bu sonuçlar Γ_pr (G)=2Γ(G) özelliğine sahip beli en az 6 olan çizgeler ve Γ_pr (G)=2Γ(G) özelliğine sahip üçgensiz kaktüs çizgelerinin karakterizasyonlarını içermektedir.

Özet (Çeviri)

Independence and domination are two related graph theory concepts, which have many applications in computer science. In this thesis, we are mainly interested in independence and domination related problems. In particular, this thesis covers two topics: almost well-dominated graphs and paired domination. We introduce almost well-dominated graphs as graphs with only two different sizes of minimal dominating sets, where the difference between these two sizes is one. We obtain a complete structural characterization for almost well-dominated graphs without induced cycles of sizes 3, 4, 5, and 7. Next, we proceed with almost well-dominated bipartite graphs. We initially establish an upper bound for the order of bipartite graphs with domination gap k, where k≥1, and minimum degree at least two. We then give a complete structural characterization of almost well-dominated bipartite graphs with minimum degree at least two. Paired domination is another topic of interest in this thesis. We particularly focus on two graph parameters: upper domination number, which is denoted by Γ(G), and upper paired domination number, which is denoted by Γ_pr (G). We specify the relationship between these two parameters by proving that Γ_pr (G)≤2Γ(G) for any graph G. As a first step, we determine the structure of bipartite and unicyclic graphs with Γ_pr (G)=2Γ(G) by characterizing such graphs. Next, we obtain two other characterization results: one for graphs with Γ_pr (G)=2Γ(G) and girth at least 6 and the other for triangle-free cactus graphs with Γ_pr (G)=2Γ(G).

Benzer Tezler

  1. Gaspıralı ve Gökalp'in eğitim anlayışları ve karşılaştırılması

    Gaspirali and Gokalp's models in education and their comparison

    SELEN YAKAR

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Eğitim ve ÖğretimAnkara Üniversitesi

    Tarih Ana Bilim Dalı

    DOÇ. DR. CİHAT AYDOĞMUŞOĞLU

  2. Olası bir İran iç savaşının Türkiye'ye etkileri

    The efects of a possible Iranian civil war on Turkey

    YUNUS EMRE SARAÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    2020

    Uluslararası İlişkilerGaziantep Üniversitesi

    Güvenlik Stratejileri ve Yönetimi Ana Bilim Dalı

    PROF. DR. MEHMET EMİN SÖNMEZ

  3. Le rapport des droits de l'homme au politique: Lefort et Rancière

    İnsan haklarının politik-olan bağlantısı: Lefort ve Rancière

    EYLEM YOLSAL MURTEZA

    Doktora

    Fransızca

    Fransızca

    2022

    FelsefeGalatasaray Üniversitesi

    Felsefe Ana Bilim Dalı

    PROF. DR. ALİYE KARABÜK KOVANLIKAYA

  4. Türk ve dünya bankacılık sisteminde ihracat kredileri ile ihracat kredi sigorta / garanti programlarının yeri ve ülke uygulamaları

    Başlık çevirisi yok

    FARUK GÜLMÜŞ

    Yüksek Lisans

    Türkçe

    Türkçe

    2001

    BankacılıkMarmara Üniversitesi

    Bankacılık Ana Bilim Dalı

    PROF.DR. İLHAN ULUDAĞ

  5. İstanbul'da eğitim donatımlarının planlanmasına ve uygulanmasına yönelik model araştırması

    Model research on planning and application of education infrastructures in Istanbul

    SUAT ÇABUK

    Doktora

    Türkçe

    Türkçe

    2003

    Şehircilik ve Bölge Planlamaİstanbul Teknik Üniversitesi

    Şehir ve Bölge Planlama Ana Bilim Dalı

    PROF. DR. YÜCEL ÜNAL