On 2-Step and Hop Dominating Sets in Graphs

Two vertices in a graph are said to 2-step dominate each other if they are at distance 2 apart. A set S of vertices in a graph G is a 2-step dominating set of G if every vertex is 2-step dominated by some vertex of S. A subset S of vertices of G is a hop dominating set if every vertex outside S is 2-step dominated by some vertex of S. The hop domination number, γ_h(G) , of G is the minimum cardinality of a hop dominating set of G. It is known that for a connected graph G, γ_h(G) = | V(G) | if and only if G is a complete graph. We characterize the connected graphs G for which γ_h(G) = | V(G) | - 1 , which answers a question posed by Ayyaswamy and Natarajan [An. Stt. Univ. Ovidius Constanta 23(2):187–199, 2015]. We present probabilistic upper bounds for the hop domination number. We also prove that almost all graphs G= G(n, p(n)) have a hop dominating set of cardinality at most the total domination number if p(n) ≪ 1 / n, and almost all graphs G= G(n, p(n)) have a hop dominating set of cardinality at most 1 + np(1 + o(1)) , if p is constant. We show that the decision problems for the 2-step dominating set and hop dominating set problems are NP-complete for planar bipartite graphs and planar chordal graphs.