A new method proposed using Malatya centrality values to find the dominating set in graphs

The dominating set problem is a widely studied problem in graph theory and falls into the group of NP-Complete problems in terms of complexity. Therefore, the studies carried out to date to solve this problem can be grouped into three groups. They can be grouped as heuristic methods, exact methods, and approximate methods. The heuristic methods are methods that are not robust and cannot always give the same result for the same graph, and these methods are probability*based and complexity analyses are often not performed. In the exact methdos, all feasible solutions are tried and then the solution is presented. These methods guarantee a minimum solution for the graphs they work with, but their time or space complexity is exponential. The methods in the last group are methods that do not have minimum solution claims, nor do they make definitive claims about the approximate solution. The concept of Second Malatya Centrality was used in the this thesis study, and it was the first thesis study in which this method was used. After showing with comments that the Second Malatya Centrality concept can be used to solve the dominating set problem, the implementation of the proposed method was carried out and the results were obtained from the implementation. In this thesis, is is claimed that the Second Malatya Centrality concept can be used to solve the Dominating Set Problem, which is one of the graph theory problems. It will ensure that the proposed method which is based on the Second Malatya Centrality conept, the time and space complexities of the propoed method are polynomial. It was revealed that the proposed method obtained the minimum solution for some graph groups, and in the remaining graphs, it was revealed that it could obtain results very close to the minimum solution (such as finding a solution with one more node than the minimum solution).