Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

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 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 $\mathrm{ud}^*$ under each of the two requirements separately, giving the Full-Cover variant $\mathrm{ud}^*_0$ and the Non-Overlapping variant $\mathrm{ud}^*_+$. The two behave very differently: on arbitrarily large graphs $\mathrm{ud}^*_0$ may remain bounded by a constant, whereas $\mathrm{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 $\lceil \sqrt[c]{n} \rceil$ and $4\sqrt{n}$, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.

Authors

Publication Details

Journal
HAL
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21210
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

Florent Foucaud, Yan Gérard, Christian Laforest, Le Vu Pham
HAL
Advanced Graph Theory Research
preprint

Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity

Florent Foucaud, Yan Gérard, Christian Laforest, Le Vu Pham
preprint en

Abstract

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 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 $\mathrm{ud}^*$ under each of the two requirements separately, giving the Full-Cover variant $\mathrm{ud}^*_0$ and the Non-Overlapping variant $\mathrm{ud}^*_+$. The two behave very differently: on arbitrarily large graphs $\mathrm{ud}^*_0$ may remain bounded by a constant, whereas $\mathrm{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 $\lceil \sqrt[c]{n} \rceil$ and $4\sqrt{n}$, respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.

HAL
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon