{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-16","reactions":{}}