2026/05/20 by Sandip Das, Sweta Das, Sk Samim Islam · 1 voice
Computer Science · Mathematics · #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2605.20970
The domination problem is a well-studied problem in graph theory. In this paper, we study two natural variants: the hop domination problem and the 2-step domination problem. Let G be a graph with vertex set V and edge set E. For a graph G, a subset S ⊆ V(G) is called an hop dominating set if every vertex not in S lies at distance of exactly 2 from at least one vertex in S. For v∈ V(G), let N(v,2) denote the set of vertices in V(G) that are at distance exactly 2 from v. For a graph G, a subset S ⊆ V(G) is called an 2-step dominating set if every vertex v∈ V(G) lies at a distance of exactly 2 from at least one vertex in S. The Hop Domination (HD) problem and the 2-Step Domination (2SD) problems ask whether a graph contains a hop domination set or a 2-step domination set of size at most k, respectively. We study the computational complexity of these problems, and show that both are NP-complete, even when restricted to d-regular graphs for every d≥ 3, claw-free graphs and also unit disk graphs.