Domination Number of Grid Graphs

Abstract

In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP-complete decision problem in computational complexity theory.Therefore, it is believed that there may be no efficient algorithm that finds a smallest dominating set for all graphs, although there are efficient approximation algorithms, as well as both efficient and exact algorithms for certain graph classes, in this study, we will investigate various categories of dominating sets in diverse graphs