A dominating set within a graph comprises a selection of its vertices where every vertex of the graph is either a member of this selection or linked to at least one member of the selection. A 1-fair dominating set is a dominating set where every vertex not included in this set is adjacent to exactly one vertex of the set. The domination problem and the 1-fair domination problem both seek to identify a dominating set and a 1-fair dominating set of a graph, respectively, with the smallest possible cardinality. The decision versions of these problems ask whether a graph has a dominating set or 1-fair dominating set of size \(\leqslant k\) . In this paper, if a problem is deemed NP-complete, it implies that its decision version is NP-completeness. Both the domination and 1-fair domination problems are NP-complete for general graphs, and the domination problem on grid graphs is NP-complete. However, the complexity of the 1-fair domination problem remains unknown for grid graphs. In this paper, we will investigate the 1-fair domination problem for extended supergrid graphs, which naturally extend grid graphs and encompass grid and supergrid graphs as subclasses. We will establish the NP-completeness of the 1-fair domination problem for these graph classes. Additionally, we will explore the 1-fair domination problem on rectangular supergrid graphs and then propose a linear-time algorithm for its solution.

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

The 1-Fair Domination Problem on Extended Supergrid Graphs

  • De-Yu Wang,
  • Ruo-Wei Hung,
  • Jong-Shin Chen,
  • Fu-Hsing Wang

摘要

A dominating set within a graph comprises a selection of its vertices where every vertex of the graph is either a member of this selection or linked to at least one member of the selection. A 1-fair dominating set is a dominating set where every vertex not included in this set is adjacent to exactly one vertex of the set. The domination problem and the 1-fair domination problem both seek to identify a dominating set and a 1-fair dominating set of a graph, respectively, with the smallest possible cardinality. The decision versions of these problems ask whether a graph has a dominating set or 1-fair dominating set of size \(\leqslant k\) . In this paper, if a problem is deemed NP-complete, it implies that its decision version is NP-completeness. Both the domination and 1-fair domination problems are NP-complete for general graphs, and the domination problem on grid graphs is NP-complete. However, the complexity of the 1-fair domination problem remains unknown for grid graphs. In this paper, we will investigate the 1-fair domination problem for extended supergrid graphs, which naturally extend grid graphs and encompass grid and supergrid graphs as subclasses. We will establish the NP-completeness of the 1-fair domination problem for these graph classes. Additionally, we will explore the 1-fair domination problem on rectangular supergrid graphs and then propose a linear-time algorithm for its solution.