ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


M.A. Henning

Michael A. Henning

University of Johannesburg



S. Pal

Saikat Pal

Department of Applied Mathematics.
Indian Institute of Technology(ISM), Dhanbad
Dhanbad, Jharkhand-826004


D. Pradhan

Dinabandhu Pradhan

Department of Mathematics and Computing, Indian Institute of Technology (ISM), Dhanbad



Hop domination in chordal bipartite graphs



Discussiones Mathematicae Graph Theory 43(3) (2023) 825-840

Received: 2020-11-21 , Revised: 2021-03-12 , Accepted: 2021-03-18 , Available online: 2021-04-14 ,


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.


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


  1. S.K. Ayyaswamy and C. Natarajan, Hop domination in graphs, manuscript.
  2. S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan and Y.B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proc. Indian Acad. Sci. Math. Sci. 125 (2015) 449–455.
  3. A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM, Philadelphia, PA, USA, 1999).
  4. Y. Caro, A. Lev and Y. Roditty, Some results in step domination of graphs, Ars Combin. 68 (2003) 105–114.
  5. M.S. Chang, Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs, 7th ISAAC, Lecture Notes in Comput. Sci. 1178 (1996) 146–155.
  6. G. Chartrand, F. Harary, M. Hossain and K. Schultz, Exact $2 $-step domination in graphs, Math. Bohem. 120 (1995) 125–134.
  7. X. Chen and Y. Wang, On total domination and hop domination in diamond-free graphs, Bull. Malays. Math. Sci. Soc. 43 (2020) 1885–1891.
  8. P. Damaschke, H. Müller and D. Kratsch, Domination in convex and chordal bipartite graphs, Inform. Process. Lett. 36 (1990) 231–236.
  9. G. Dror, A. Lev and Y. Roditty, A note: some results in step domination of trees, Discrete Math. 289 (2004) 137–144.
  10. F. Foucaud, Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes, J. Discrete Algorithms 31 (2015) 48–68.
  11. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).
  12. T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker Inc., New York, 1998).
  13. M.A. Henning and N. Jafari Rad, On $2$-step and hop dominating sets in graphs, Graphs Combin. 33 (2017) 913–927.
  14. M.A. Henning, S. Pal and D. Pradhan, Algorithm and hardness results on hop domination in graphs, Inform. Process. Lett. 153 (2020) 105872.
  15. P. Hersh, On exact $n$-step domination, Discrete Math. 205 (1999) 235–239.
  16. M. Farhadi Jalalvand and N. Jafari Rad, On the complexity of k-step and k-hop dominating sets in graphs, Math. Montisnigri 40 (2017) 36–41.
  17. S. Kundu and S. Majumder, A linear time algorithm for optimal $k$-hop dominating set of a tree, Inform. Process. Lett. 116 (2016) 197–202.
  18. H. Müller and A. Brandstädt, The NP-completeness of Steiner Tree and Dominating Set for chordal bipartite graphs, Theoret. Comput. Sci. 53 (1987) 257–265.
  19. C. Natarajan and S.K. Ayyaswamy, Hop domination in graphs-II, An. Stiint. Univ. ``Ovidius'' Constanta Ser. Mat. 23 (2015) 187–199.
  20. C. Natarajan and S.K. Ayyaswamy, A note on the hop domination number of a subdivision graph, Int. J. Appl. Math. 32 (2019) 381–390.
  21. C. Natarajan, S.K. Ayyaswamy and G. Sathiamoorthy, A note on hop domination number of some special families of graphs, Int. J. Pure Appl. Math. 119 (2018) 14165–14171.
  22. B.S. Panda and D. Pradhan, Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs, J. Comb. Optim. 26 (2013) 770–785.
  23. D. Pradhan, Complexity of certain functional variants of total domination in chordal bipartite graphs, Discrete Math. Algorithms Appl. 4(3) (2012) 1250045.
  24. Y.M. Pabilona and H.M. Rara, Connected hop domination in graphs under some binary operations, Asian-Eur. J. Math. 11 (2018) 1850075.
  25. H. Rahbani, N. Jafari Rad and M.R. Sadeghi, A note on the complexity of locating-total domination in graphs, Theoret. Comput. Sci. 799 (2019) 32–39.
  26. R.C. Rakim, C.J.C. Saromines and H.M. Rara, Perfect hop domination in graphs, Appl. Math. Sci. 12 (2018) 635–649.
  27. R. Uehara, Linear time algorithms on chordal bipartite and strongly chordal graphs, in: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 2380 (2002) 993–1004.