Fair Domination on Extended Supergrid Graphs: Complexity, Linear-Time Algorithms, and ILP Formulations
Mathematics · 2026-03-11 · 14 (6) · 947
DOI: 10.3390/math14060947 ↗At a glance
Journal article in Mathematics, published online on 2026-03-11. Written by Ruo-Wei Hung. 24 references. The full text is freely available (open access, CC BY 4.0). Funded by: National Science and Technology Council.
Abstract (original language)
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.
Funding
- National Science and Technology Council
Cite
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