Fair Domination on Extended Supergrid Graphs: Complexity, Linear-Time Algorithms, and ILP Formulations
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.
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}
}
EUVIMED