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, $$\gamma _{h}(G)$$ γ h ( G ) , of G is the minimum cardinality of a hop dominating set of G. It is known that for a connected graph G, $$\gamma _{h}(G) = |V(G)|$$ γ h ( G ) = | V ( G ) | if and only if G is a complete graph. We characterize the connected graphs G for which $$\gamma _{h}(G) = |V(G)|-1$$ γ 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))$$ G = G ( n , p ( n ) ) have a hop dominating set of cardinality at most the total domination number if $$p(n)\ll 1/n$$ p ( n ) ≪ 1 / n , and almost all graphs $$G=G(n,p(n))$$ G = G ( n , p ( n ) ) have a hop dominating set of cardinality at most $$1+np(1+o(1))$$ 1 + n p ( 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.