Secure Hop Dominating Sets in Graphs

Abstract

Let $G$ be an undirected (simple) graph with vertex and edge sets $V(G)$ and $E(G)$, respectively.  A hop dominating set $S$ in $G$ is secure hop dominating if for each $v\in V(G) \setminus S$, there exists $w \in S \cap N_G^2(v)$ such that $(S\setminus \{w\}) \cup \{v\}$ is hop dominating in $G$. The minimum cardinality of a  secure hop dominating in $G$, denoted by $\gamma_{sh}(G)$, is called the secure hop domination number of $G$.  In this paper, we show that the difference $\gamma_{sh}(G-\gamma_h(G)$ can be made arbitrarily large, where $\gamma_h(G)$ is the hop domination number of $G$. We give bounds on the secure hop domination number and characterize those graphs which attain these bounds. The value of the newly defined parameter is determined for some classes of graphs. Moreover, we characterize the secure hop dominating sets in the shadow graph and complementary prism and determine the value of the parameter for each of these graphs.