Graflarda Roma baskınlık sayısı

Abstract

Bir graf G=(V,E), V tepeler kümesi ve E ayrıtlar kümesi olacak şekilde, tepe ikililerinden oluşan bir küme ikilisidir. Zedelenebilirlik, bir G grafı birleştirilmemiş bir graf olana kadar bazı tepe veya ayrıtların kaldırılmasına karşı grafın dayanıklılığıdır. Graf teorisinde, zedelenebilirlikle ilgili birçok parametre vardır. Son yıllarda dikkat çeken bir graf teorisi parametresi graflarda baskınlıktır.Graflarda birçok baskın küme modelleri vardır. Bu tezde, graflarda özel bir baskınlık türü olan Roma baskınlığı üzerine çalışılmıştır. Yapılan çalışmada literatürde henüz Roma Baskınlık sayıları yer almayan bazı grafların Roma Baskınlık sayıları hesaplanarak, hesaplama sonuçları genelleştirilmiş ve genel sonuçlar ispatları ile verilmiştir. Bu tez, beş bölümden oluşmaktadır. İlk olarak graf teorisinin temellerinin nasıl atıldığına, bilinen uygulama alanlarına ve bazı zedelenebilirlik ölçümlerine ayrıntılı olarak değinilmiştir. Bilinen ölçüm türlerinden olan baskınlık sayısı ile Roma baskınlık sayısı ele alınmıştır. Bununla birlikte, baskınlık sayısını literatüre kazandıran satranç problemi ve Roma baskınlık sayısını literatüre kazandıran Roma baskınlığı problemi hakkında bilgilere yer verilmiştir. İkinci bölümde graf teorisinin temellerinin oturduğu tanım ve teoremler ayrıntılı bir şekilde verilmiştir. Üçüncü bölümde, materyal ve yöntemler ile graflarda baskınlık, Roma baskınlığı ve Mycielski inşası ile bir grafın Mycielski grafı kavramları açıklanmış ve bir örnek ile konuya ışık tutulmuştur. Dördüncü bölümde, kuyruklu yıldız graf, çift kuyruklu yıldız graf ve tarak graflarda Roma baskınlık sayısına ve bunların Mycielski inşası yöntemi ile elde edilen Mycielski graflarının Roma baskınlık sayılarına ilişkin elde edilen veriler, teoremler ve ispatlar halinde verilmiştir. Ayrıca, herhangi bir graf için Roma baskınlık sayısını hesaplamayı sağlayan Roma baskınlığı algoritması da bu bölümde sunulmuştur. Son bölümde ise çalışmadan elde edilen sonuçlara ve önerilere yer verilmiştir.

A graph is a pair of sets G=(V,E), where V is the set of vertices and E is the set of edges, formed by pairs of vertices. The vulnerability is the durability of the graph, against the removal of some vertices or edges, until the graph G is an unconnected graph. In graph theory, there are many parameters related to vulnerability. A parameter of graph theory that has received attention during recent decades is that of domination in graphs.There are many models of dominating sets in graphs. In this thesis, Roman domination, a special type of domination in graphs, has been studied. In the study, the Roman Domination numbers of some graphs that do not have Roman Domination numbers in the literature are calculated, the calculation results are generalized, and the general results are given with proofs.This thesis consists of five chapters.Firstly, how the foundations of the Graph Theory were laid, known application areas, and some vulnerability measurements were touched upon in detail. Domination number and Roman domination number, which are the known measurement types, have been discussed. In addition, information is given about the chess problem that brought the domination number to the literature and the Roman domination problem that brought the Roman domination number to the literature. In the second chapter, the basic definitions and theorems of graph theory are given in detail. In the third chapter, the concepts of domination in graphs, Roman domination and Mycielski construction, and the Mycielski graph of a graph are explained by materials and methods, and the subject is enlightened with an example. In the fourth chapter, the data obtained regarding the Roman domination number of comet graph, double-comet graph, and comb graphs, and also the Roman domination numbers of the Mycielski graphs obtained by the Mycielski construction method are given as theorems and proofs. Also, the Roman domination algorithm, which allows the calculation of the Roman domination number for any graph, is presented in this section. In the last part, results and suggestions obtained from the study are included.