The 1-Fair Domination Problem on Extended Supergrid Graphs
摘要
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.