## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 913-927 |

Number of pages | 15 |

Journal | Graphs and Combinatorics |

Volume | 33 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Jul 2017 |

## Keywords

- 2-Step dominating set
- Hop dominating set
- NP-complete

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics