Id: arxiv/2611.21210 Url: https://arxiv.org/abs/2611.21210 Tags: cs.DM, math.CO Score: 0 Title: Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity Domain: cs.DM Source: arxiv Authors: Florent Foucaud, Yan Gerard, Christian Laforest, Le Vu Pham Reviews: 0 Subject: cs.DM Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-16 Page: https://delphi.science/r/arxiv/2611.21210 A vertex is uni-dominated by a set $S \subseteq V(G)$ if exactly one vertex of $S$ lies in its closed neighborhood, and the uni-domination number $\mathrm{ud}^*(G)$ is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with $\mathrm{ud}^*(G) = n$. Hedetniemi and Rall asked for the largest constant $c$ with $\mathrm{ud}^*(T) \geq c \cdot 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…