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
- Tez No: 689342
- Danışmanlar: DOÇ. DR. DİDEM GÖZÜPEK KOCAMAN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2021
- Dil: İngilizce
- Üniversite: Gebze Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2020
Eğitim ve ÖğretimAnkara ÜniversitesiTarih Ana Bilim Dalı
DOÇ. DR. CİHAT AYDOĞMUŞOĞLU
- 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
2020
Uluslararası İlişkilerGaziantep ÜniversitesiGüvenlik Stratejileri ve Yönetimi Ana Bilim Dalı
PROF. DR. MEHMET EMİN SÖNMEZ
- 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
2022
FelsefeGalatasaray ÜniversitesiFelsefe Ana Bilim Dalı
PROF. DR. ALİYE KARABÜK KOVANLIKAYA
- İ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
2003
Şehircilik ve Bölge Planlamaİstanbul Teknik ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
PROF. DR. YÜCEL ÜNAL