Analytical Validation of the Malatya Dominating Set Algorithm: Constructing Optimal Dominating Sets Without Redundant Nodes

This study focuses on the theoretical proof of the Malatya Dominating Set Algorithm (MDSA). MDSA is a dominating set determination algorithm that combines greedy and dynamic programming techniques by using the concept of centrality and thus produces optimum or near-optimum solutions. In the previous study, the MDSA algorithm has been experimentally implemented on various datasets and successful results have been obtained. However, these experimental successes need to be proven analytically with theoretical evidence. For this purpose, in this study, it is analytically proven that MDSA produces optimum or near-optimum results on some special graph types (paths, cycles, star graphs, two-sided graphs, etc.). In the study, it is examined in detail how MDSA produces the minimum dominant set when applied to specific graph structures. In the proof process, it is mathematically shown how centrality calculations affect the selection of dominating set and how the algorithm produces redundant-free dominating set by eliminating unnecessary nodes. In conclusion, this study strengthens the theoretical foundations of MDSA and analytically demonstrates its advantages in certain graph types when compared to other dominating set algorithms in the literature.