S. Shanmugavelan     (Srinivasa Ramanujan Centre, SASTRA Deemed to be University, Kumbakonam–612001, India)
C. Natarajan     (Srinivasa Ramanujan Centre, SASTRA Deemed University, Kumbakonam-612001, India)


A subset \( H \subseteq V (G) \) of a graph \(G\) is a hop dominating set (HDS) if for every \({v\in (V\setminus H)}\) there is at least one vertex  \(u\in H\) such that \(d(u,v)=2\).  The minimum cardinality of a hop dominating set of \(G\) is called the hop domination number of \(G\) and is denoted by \(\gamma_{h}(G)\). In this paper, we compute the hop domination number for triangular and quadrilateral snakes. Also, we analyse the hop domination number of graph families such as generalized thorn path, generalized ciliates graphs, glued path graphs and generalized theta graphs.


Hop domination number, Snake graphs, Theta graphs, Generalized thorn path

Full Text:



  1. Ayyaswamy S.K., Natarajan C. Hop Domination in Graphs. Manuscript, 2015. 
  2. Ayyaswamy S.K., Krishnakumari B., Natarajan C., Venkatakrishnan Y.B. Bounds on the hop domination number of a tree. Proc. Math. Sci., 2015. Vol. 125, No. 4. P. 449-455. DOI: 10.1007/s12044-015-0251-6
  3. Balakrishnan R., Ranganathan K. A Textbook of Graph Theory, 2nd ed. NY: Springer, 2012. 292 p. DOI: 10.1007/978-1-4614-4529-6
  4. Durgun D.D., Lökçü B. Weak and strong domination in thorn graphs. Asian-Eur. J. Math., 2020. Vol. 13, No. 4. Art. no. 2050071. DOI: 10.1142/S1793557120500710
  5. Gallian J.A. A dynamic survey of graph Labeling. Electron. J.  Combin., 2021. Art. no. DS6. P. 1–576. DOI: 10.37236/27
  6. Getchial Pon Packiavathi P., Balamurugan S., Gnanajothi R.B. Hop domination number of caterpillar graphs. Adv. Math. Sci. J., 2020. Vol. 9, No. 5. P. 2739–2748. DOI: 10.37418/amsj.9.5.36
  7. Gutman I. Distance in thorny graph. Publ. Inst. Math. (Beograd) (N.S.), 1998. Vol. 63, No. 83. P. 31–36. URL: http://eudml.org/doc/258067
  8. Haynes T.W., Hedetniemi S.T., Henning M.A. Topics in Domination in Graphs. Cham: Springer, 2020. 545 p. DOI: 10.1007/978-3-030-51117-3
  9. Haynes T.W., Hedetniemi S.T., Slater P.J. Fundamentals of Domination in Graphs. Boca Raton: CRC Press, 1998. 464 p. DOI: 10.1201/9781482246582
  10. Haynes T.W., Hedetniemi S.T., Slater P.J. Domination in Graphs–Advanced Topics. Boca Raton: CRC Press, 1998. 520 p. DOI: 10.1201/9781315141428
  11. Henning M.A., Rad N.J. On 2-step and hop dominating sets in graphs. Graphs Combin., 2017. Vol. 33. P. 913–927. DOI: 10.1007/s00373-017-1789-0
  12. Henning M.A., Pal S., Pradhan D. Algorithm and hardness results on hop domination in graphs. Inform. Process. Lett., 2020. Vol. 153. P. 1–8. DOI: 10.1016/j.ipl.2019.105872
  13. Natarajan C., Ayyaswamy S.K. Hop domination in graphs-II. An. St. Univ. Ovidius Constanta, 2015. Vol. 23. No. 2. P. 187–199. DOI: 10.1515/auom-2015-0036
  14. Natarajan C., Ayyaswamy S.K., Sathiamoorthy G. A note on hop domination number of some special families of graphs. Int. J. Pure Appl. Math., 2018. Vol. 119. No. 12f. P. 14165–14171. URL: https://www.acadpubl.eu/hub/2018-119-12/articles/6/1314.pdf 
  15. Pabilona Y.M., Rara H.M. Connected hop domination in graphs under some binary operations. Asian-Eur. J. Math., 2018. Vol. 11. No. 5 .P. 1–11. DOI: 10.1142/S1793557118500754 
  16. Rad N.J., Poureidi A. On hop Roman domination in trees. Comm. Combin. Optim., 2019. Vol. 4. No. 2. P. 201–208. DOI: 10.22049/CCO.2019.26469.1116 
  17. Rakim R.C., Saromines Ch.J.C., Rara H.M. Perfect hop domination in graph. Appl. Math. Sci., 2018. Vol. 12. No. 13. P. 635–649. DOI: 10.12988/ams.2018.8576
  18. Salasalan G.P., Canoy S.R., Jr Global hop domination numbers of graphs. Eur. J. Pure Appl. Math., 2021. Vol. 14, No. 1. P. 112–125. DOI: 10.29020/nybg.ejpam.v14i1.3916
  19. Sathiyamoorthy G., Janakiraman T.N. Graceful labeling of generalized theta graphs. Nat. Acad. Sci. Lett., 2018. Vol. 41. No. 2. P. 121–122. DOI: 10.1007/s40009-018-0625-2 
  20. Shanmugavelan S., Natarajan C. An updated survey on distance-based domination parameters in graphs. Asia Math., 2020. Vol. 4. No. 2. P. 134–149. URL: http://www.asiamath.org/article/vol4iss2/AM-2008-4207.pdf

DOI: http://dx.doi.org/10.15826/umj.2021.2.009

Article Metrics

Metrics Loading ...


  • There are currently no refbacks.