A Study on Dominating Set: NP-Hardness and Polynomial Results
摘要
In graph theory, a dominating set for a graph G is a subset D of its vertices such that any vertex of G is in D or has a neighbor in D. The domination number \(\gamma (G)\) represents the minimum size of a dominating set for G. While computing \(\gamma (G)\) for all graphs is an NP-hard problem, many approximation algorithms exist, along with exact algorithms for specific graph classes. In this paper, some selected recent results on domination set in graphs are shown. A technique called decreasing graph will be developed to show that the problem can be solved in polynomial time in some graph classes. These results extend some previous ones.