← 研踪 PaperTrailarXiv:2611.21210 · v1
Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity
首次提交 2026-11-16 23:02
版本更新 2026-11-16 23:02
雷达观测 2026-11-17 16:10
摘要
A vertex is uni-dominated by a set if exactly one vertex of lies in its closed neighborhood, and the uni-domination number is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with . Hedetniemi and Rall asked for the largest constant with for every tree of order . We answer their question: the constant is , 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 under each of the two requirements separately, giving the Full-Cover variant and the Non-Overlapping variant . The two behave very differently: on arbitrarily large graphs may remain bounded by a constant, whereas 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 and , respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.
作者备注:23 pages, 5 figures. Appears in the Proceedings of the 52nd International Conference on Current Trends in Theory and Practice of Computer Science (Sofsem 2027)
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-16 23:02 · 最新观测版本
Full-Cover and Non-Overlapping Uni-domination in Graphs: Bounds and Complexity
A vertex is uni-dominated by a set if exactly one vertex of lies in its closed neighborhood, and the uni-domination number is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with . Hedetniemi and Rall asked for the largest constant with for every tree of order . We answer their question: the constant is , 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 under each of the two requirements separately, giving the Full-Cover variant and the Non-Overlapping variant . The two behave very differently: on arbitrarily large graphs may remain bounded by a constant, whereas 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 and , respectively, the latter even on split graphs. Finally, we show that neither of the two parameters bounds the other.
查看此版本解读 →查看此版本原文 ↗