EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Fair Domination on Extended Supergrid Graphs: Complexity, Linear-Time Algorithms, and ILP Formulations

Ruo-Wei Hung

Mathematics · 11.03.2026 · 14 (6) · 947

DOI: 10.3390/math14060947 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics, online erschienen am 11.03.2026. Verfasst von Ruo-Wei Hung. Die Arbeit nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science and Technology Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A dominating set of a graph is a subset of vertices such that every vertex is either contained in the set or adjacent to at least one vertex in it. A dominating set is called k-fair if each vertex not in this set is adjacent to exactly k vertices of the set. The domination and k-fair domination problems aim to find such sets of minimum cardinality. Both problems are NP-complete for general graphs, and the domination problem remains NP-complete on grid graphs, whereas the k-fair domination problem remains open on grid graphs. In this paper, we study the 1-fair and 2-fair domination problems on extended supergrid graphs, which generalize grid graphs and include both grid and supergrid graphs as subclasses. We prove that the 1-fair domination problem is NP-complete for these graph classes, even when restricted to planar graphs with maximum degree 4. On the positive side, for rectangular supergrid graphs, we present a linear-time algorithm for computing minimum 1-fair dominating sets. In addition, we formulate an integer linear programming (ILP) model to investigate the 1-fair and 2-fair dominations on small instances and introduce a restricted k-fair domination problem motivated by the experimental observations.

Förderung

  • National Science and Technology Council

Zitieren

APA

Hung, R. (2026). Fair Domination on Extended Supergrid Graphs: Complexity, Linear-Time Algorithms, and ILP Formulations. Mathematics, 14(6), 947. https://doi.org/10.3390/math14060947

Vancouver

Hung R. Fair Domination on Extended Supergrid Graphs: Complexity, Linear-Time Algorithms, and ILP Formulations. Mathematics. 2026;14(6):947. doi:10.3390/math14060947

BibTeX
@article{Hung2026,
  author = {Hung, Ruo-Wei},
  title = {Fair Domination on Extended Supergrid Graphs: Complexity, Linear-Time Algorithms, and ILP Formulations},
  journal = {Mathematics},
  year = {2026},
  volume = {14},
  number = {6},
  pages = {947},
  doi = {10.3390/math14060947}
}
Kostenlos starten →