On Hop Roman Domination in Trees

Document Type : Original paper


1 Separtment of Mathemtics, Shahed University, Tehran, Iran

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


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


Main Subjects