Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity
Abstract
A vertex is uni-dominated by a set S ⊆ V (G) if exactly one vertex of S lies in its closed neighborhood, and the uni-domination number ud * (G) is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with ud * (G) = n. Hedetniemi and Rall asked for the largest constant c with ud * (T ) ≥ c • n for every tree T of order n. We answer their question: the constant is 4/5, and a set attaining it can be computed in linear time. This set is moreover a dominating set. Recall that an efficient dominating set satisfies two requirements at once: it dominates every vertex, and it dominates no vertex twice. Our set satisfies the first one, which leads us to study ud * under each of the two requirements separately, giving the Full-Cover variant ud * 0 and the Non-Overlapping variant ud * + . The two behave very differently: on arbitrarily large graphs ud * 0 may remain bounded by a constant, whereas ud * + always grows with the order. We present bounds for both, and show that the associated decision problems are polynomial for constant thresholds and NP-complete for the thresholds ⌈ c √ n⌉ and 4 √ n, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.
Related
- On k-limited domination: complexity and Sierpiński graphs
- The parameterised complexity of generalised temporal domination on temporal graphs with modular structure
- Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms
- On k-limited domination: complexity and Cartesian products
- Bounds for the ratio between the independent domination number and the domination number
BibTeX
@misc{foucaud2026fullcover,
title = {{Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity}},
author = {Florent Foucaud and Yan Gerard and Christian Laforest and Le Vu Pham},
howpublished = {HAL},
year = {2026},
month = sep,
url = {https://hal.science/hal-05768708v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity
AU - Florent Foucaud
AU - Yan Gerard
AU - Christian Laforest
AU - Le Vu Pham
PY - 2026
DA - 2026/09/29
PB - HAL
UR - https://hal.science/hal-05768708v1
AB - A vertex is uni-dominated by a set S ⊆ V (G) if exactly one vertex of S lies in its closed neighborhood, and the uni-domination number ud * (G) is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with ud * (G) = n. Hedetniemi and Rall asked for the largest constant c with ud * (T ) ≥ c • n for every tree T of order n. We answer their question: the constant is 4/5, and a set attaining it can be computed in linear time. This set is moreover a dominating set. Recall that an efficient dominating set satisfies two requirements at once: it dominates every vertex, and it dominates no vertex twice. Our set satisfies the first one, which leads us to study ud * under each of the two requirements separately, giving the Full-Cover variant ud * 0 and the Non-Overlapping variant ud * + . The two behave very differently: on arbitrarily large graphs ud * 0 may remain bounded by a constant, whereas ud * + always grows with the order. We present bounds for both, and show that the associated decision problems are polynomial for constant thresholds and NP-complete for the thresholds ⌈ c √ n⌉ and 4 √ n, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.
ER -