New structural aspects of domination and independence in graph theory

Abstract

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