A NOTE ON THE HOP DOMINATION NUMBER
OF A SUBDIVISION GRAPH
C. Natarajan1, S.K. Ayyaswamy2
1,2Department of Mathematics
School of Arts, Sciences and Humanities
SASTRA Deemed University
Thanjavur, 613 401, Tamilnadu, INDIA

Abstract

Let $G=(V,E)$ be a graph with $p$ vertices and $q$ edges. A subset $S \subset V(G)$ is a hop dominating set of $G$ if for every $v \in V-S$, there exists $u \in S$ such that $d(u,v)=2$. The minimum cardinality of a hop dominating set of $G$ is called a hop domination number of $G$ and is denoted by $\gamma_{h}(G)$. The subdivision graph $S(G)$ of a graph $G$ is a graph obtained by subdividing every edge of $G$ exactly once. In this paper, we obtain an upper bound on hop domination number of subdivision graph of any connected graph $G$ in terms of number of edges $q$, the maximum degree $\Delta(G)$ and domination number $\gamma(G)$ of $G$. We also characterize the family of connected graphs attaining this bound.

Citation details of the article



Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 32
Issue: 3
Year: 2019

DOI: 10.12732/ijam.v32i3.2

Download Section



Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.

References

  1. [1] S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan and Y.B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proc. of the Indian Academy of Sciences (Mathematical Sciences), 125, No 4 (2015), 449-455.
  2. [2] S.K. Ayyaswamy, C. Natarajan and Y.B. Venkatakrishnan, Hop domination in graphs, In: ICDMDS2018 Conference Proc., SASTRA (2018).
  3. [3] G. Chartrand and L. Lesniak, Graphs and Digraphs, Chapman and Hall, CRC, 4th Ed. (2005).
  4. [4] G. Chartrand, F. Harary, M. Hossain, K. Schultz, Exact 2-step domination in graphs, Mathematica Bohemica 120 (1995), 125-134.
  5. [5] M. Farhadi Jalalvand and N. Jafari Rad, On the complexity of k-step and k-hop dominating sets, Mathematica Montisnigri, 60 (2017).
  6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York (1998).
  7. [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs - Advanced Topics, Marcel Dekker, New York (1998).
  8. [8] M.A. Henning and N. Jafari Rad, On 2-step and hop dominating sets in graphs, Graphs and Combinatorics, 33, No 4 (2017), 913-927.
  9. [9] C. Natarajan and S.K. Ayyaswamy, Hop domination in graphs-II, Analele Stiintifice ale Universitatii Ovidius Constanta (ASUOC), 23, No 2 (2015), 187-199.
  10. [10] Y.M. Pabilona and H.M. Rara, Total hop dominating sets in the join, corona and lexicographic product of graphs, J. of Algebra and Applied Mathematics, 15, No 2 (2017), 103-115.
  11. [11] Y.M. Pabilona and H.M. Rara, Connected hop domination in graphs under some binary operations, Asian-European J. of Mathematics, 11, No 5 (2018).
  12. [12] N. Sridharan, V.S.A. Subramanian and M.D. Elias, Bounds on the distance two-domination number of a graph, Graphs and Combinatorics, 18 (2002), 667-675.
  13. [13] N. Sridharan, V.S.A. Subramanian and M.D. Elias, Distance two-domination and total distance two domination in subdivision graphs, Graph Theory and its Applications, Editors: R. Balakrishnan et al., Narosa Publishing House, New Delhi (2004), 121-128.