# 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