On Hop Roman Domination in Trees

Nader Jafari Rad | A. Poureidi

---

URL :   http://research.shahed.ac.ir/WSR/WebPages/Report/PaperView.aspx?PaperID=116658
Date :  2019/07/02
Publish in :    Communications in Combinatorics and Optimization
DOI :  https://doi.org/DOI: 10.22049/cco.2019.26469.1116
Link :  http://comb-opt.azaruniv.ac.ir/article_13874.html
Keywords :-hopr,domination,Domination,tree

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