Hop domination in chordal bipartite graphs

Michael A. Henning, Saikat Pal, D. Pradhan

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


In a graph G, a vertex is said to 2-step dominate itself and all the vertices which are at distance 2 from it in G. A set D of vertices in G is called a hop dominating set of G if every vertex outside D is 2-step dominated by some vertex of D. Given a graph G and a positive integer k, the hop domination problem is to decide whether G has a hop dominating set of cardinality at most k. The hop domination problem is known to be NP-complete for bipartite graphs. In this paper, we design a linear time algorithm for computing a minimum hop dominating set in chordal bipartite graphs.

Original languageEnglish
JournalDiscussiones Mathematicae - Graph Theory
Publication statusAccepted/In press - 2021


  • chordal bipartite graphs
  • domination
  • hop domination
  • polynomial time algorithm

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Hop domination in chordal bipartite graphs'. Together they form a unique fingerprint.

Cite this