NP-completeness of some generalized hop and step domination parameters in graphs

Message:
Article Type:
Research/Original Article (دارای رتبه معتبر)
Abstract:
‎Let $r\geq 2$. A subset $S$ of vertices of a graph $G$ is a $r$-hop independent dominating set if every vertex outside $S$ is at distance $r$ from a vertex of $S$, and for any pair $v, w\in S$, $d(v, w)\neq r$. A $r$-hop Roman dominating function ($r$HRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v \in V$ with $f(v) = 0$ there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$-step Roman dominating function ($r$SRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v$ with $f(v)=0$ or $2$, there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$HRDF $f$ is a $r$-hop Roman independent dominating function if for any pair $v, w$ with non-zero labels under $f$, $d(v, w)\neq r$. We show that the decision problem associated with each of $r$-hop independent domination, $r$-hop Roman domination, $r$-hop Roman independent domination and $r$-step Roman domination is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.
Language:
English
Published:
Communications in Combinatorics and Optimization, Volume:10 Issue: 1, Winter 2025
Pages:
181 to 193
https://www.magiran.com/p2784454