# 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 $Ssubset 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_{vin 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)=2gamma_{ch}(T)$ for a given‎
‎tree $T$.\‎
‎{bf Keywords:} hop dominating set‎, ‎connected hop dominating set‎, ‎hop Roman dominating‎
‎function‎.

Keywords

Main Subjects