On Hop Roman Domination in Trees

Document Type : Original paper

Authors

1 Separtment of Mathemtics, Shahed University, Tehran, Iran

2 Department of Mathematics, Shahrood University of Technology, Shahrood, Iran

Abstract

‎Let $G=(V,E)$ be a graph. A subset $S\subset V$ is a hop dominating set if every vertex outside $S$ is at distance two from a vertex of $S$. A hop dominating set $S$ which induces a connected subgraph is called a connected hop dominating set of $G$. The connected hop domination number of $G$, $ \gamma_{ch}(G)$, is the minimum cardinality of a connected hop dominating set of $G$. A hop Roman dominating function (HRDF) of a graph $G$ is a function $
f: V(G)\longrightarrow \{0, 1, 2\} $ having the property that for every vertex $ v \in V $ with $ f(v) = 0 $ there is a vertex $ u $ with $ f(u)=2 $ and $ d(u,v)=2 $. The weight of an HRDF $ f $ is the sum $f(V) = \sum_{v\in V} f(v) $. The minimum weight of an HRDF on $ G $ is called the hop Roman domination number of $ G $ and is denoted by $ \gamma_{hR}(G)
$. We give an algorithm that decides whether $\gamma_{hR}(T)=2\gamma_{ch}(T)$ for a given tree $T$.

Keywords

Main Subjects

References

[1] M.P. Alvarez-Ruiz, T. Mediavilla-Gradolph, S.M. Sheikholeslami, J.C. ´Valenzuela-Tripodoro, and I.G. Yero, On the strong roman domination number of graphs, Discrete Appl. Math. 231 (2017), 44–59.
[2] M. Atapour, S.M. Sheikholeslami, and L. Volkmann, Global Roman domination in trees, Graphs Combin. 31 (2015), no. 4, 813–825.
[3] S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan, and Y.B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proceedings-Mathematical Sciences 125 (2015), no. 4, 449–455.
[4] S.K. Ayyaswamy and C. Natarajan, Hop domination in graphs, Manuscript.
[5] E.J. Cockayne, P.A. Jr. Dreyer, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1, 11–22.
[6] A. Hansberg and L. Volkmann, Upper bounds on the $k$-domination number and the $k$-Roman domination number, Discrete Appl. Math. 157 (2009), no. 7, 1634–1639.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
[8] M.A. Henning and N. Jafari Rad, On 2-step and hop dominating sets in graphs, Graphs Combin. 33 (2017), no. 4, 913–927.
[9] N. Jafari Rada and E. Shabanib, On the complexity of some hop domination parameters, Elect. J. Graph Theory Appl. 7 (2019), no. 1, 74–86.
[10] C. Natarajan and S.K. Ayyaswamy, Hop domination in graphs-ii, An. Stt. Univ. Ovidius Constanta 23 (2015), no. 2, 187–199.
[11] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer Math. Monthly 107 (2000), 585–594.
[12] E. Shabani, Hop Roman domination in graphs, Manuscript (2017). 
[13] E Shabani, N Jafari Rad, and A Poureidi, Graphs with large hop Roman domination number, Computer Sci. J. Moldova 27 (2019), no. 1, 1–20.
[14] I. Stewart, Defend the Roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[15] L. Volkmann, Signed total Roman domination in digraphs, Discuss. Math. Graph Theory 37 (2017), no. 1, 261–272.
[16] L. Volkmann, The signed total Roman k-domatic number of a graph, Discuss. Math. Graph Theory 37 (2017), no. 4, 1027–1038.
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 201-208

Files

Share

How to cite

Statistics