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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Study on Dominating Set: NP-Hardness and Polynomial Results

  • Anh Son Ta,
  • Ngoc C. Lê,
  • Le Vu Pham,
  • Anh Tuan Nguyen

摘要

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.