{"id":"arxiv/2605.20970","url":"https://arxiv.org/abs/2605.20970","tags":["cs.DM","math.CO"],"score":0,"title":"On the Complexity of Hop Domination and 2-Step Domination in Graph Classes","domain":"cs.DM","source":"arxiv","authors":["Sandip Das","Sweta Das","Sk Samim Islam"],"reviews":0,"subject":"cs.DM","summary":"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 \\subseteq V(G)$ is called an \\emph{hop dominating set} if every vertex not in $S$ lies at distance of exactly $2$ from at least one vertex in $S$. For $v\\in 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 \\subseteq V(G)$ is called an \\emph{$2$-step…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-20","reactions":{}}