On Hop Roman Domination in Trees

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‎.