Tez No	İndirme	Tez Künye	Durumu
689342		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 Yazar:HADI ALIZADEH Danışman: DOÇ. DR. DİDEM GÖZÜPEK KOCAMAN Yer Bilgisi: Gebze Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2021 94 s.
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.
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).