On Pairs of Disjoint Hop Dominating Sets in Graphs

Abstract

A set $S$ of vertices of a graph $G$ is a hop dominating set of $G$ if for every  $v\in V(G)\setminus S$, $v$ is at distance $2$ from a vertex in $S$. The minimum cardinality $\gamma_h(G)$ of a hop dominating set is the hop domination number of $G$. Any hop dominating set of cardinality $\gamma_h(G)$ is a $\gamma_h$-set. A pair $(S,T)$ of sets of vertices of $G$ is a disjoint hop dominating pair if $S\cap T=\varnothing$ and both $S$ and $T$ are hop dominating sets of $G$. In particular, if $S$ is a $\gamma_h$-set, then $T$ is an inverse hop dominating set of $G$. The minimum sum $|S|+|T|$ among all disjoint hop dominating pairs is the disjoint hop domination number, denoted by $\gamma_{hh}(G)$. The minimum cardinality of an inverse hop dominating set of $G$ is the inverse hop domination number of $G$, denoted by $\widetilde{\gamma}_h(G)$. 

In this paper, we initiate the study of inverse hop domination and disjoint hop domination. Interestingly, for every pair of positive integers $m$ and $n$ with $2\le m\le n$, there exists a connected graph $G$ for which $\gamma_h(G)=m$ and $\widetilde{\gamma}_h(G)=n$. Also, for each positive integer $n\ge 4$, there exists a connected graph $G$ for which $\gamma_h(G)+\widetilde{\gamma}_h(G)-\gamma_{hh}(G)=n$. Here we investigate these new concepts for some specific graphs including the join, corona and lexicographic product of graphs.