Characterizations on the hop Roman domination in trees
Abstract
A subset S of vertices of G is a hop dominating set if every vertex outside S is at distance two from a vertex of S. The hop domination number of G, denoted by γh(G), is the minimum cardinality of a hop dominating set of G. A hop Roman dominating function (HRDF) of G is a function f : V(G) ⟶ {0, 1, 2} having the property that for every vertex v ∈ V with f(v) = 0 there is a vertex u with f(u) = 2 and d(u, v) = 2. The weight of a HRDF f is the sum f(V) = ∑v∈Vf(v). The minimum weight of HRDF on G is called the hop Roman domination number of G, and is denoted by γhR(G). In this paper we characterize all graphs G with γhR(G) = γh(G), all trees T for which γhR(T) = γh(T) + 1 as well as all trees T for which γhR(T) = γh(T) + 2.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.2.10
References
G. Asemian, N. Jafari Rad, A. Tehranian, and H. Rasouli, NP-completeness of some generalized hop and step domination parameters in graphs, Commun. Comb. Optim. 10 (2025), 181–193.
S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan, and Y.B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proceedings of Math. Sci., Indian Academy of Science 125 (2015), 449–455.
M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Roman Domination in Graphs. In: Haynes T.W., Hedetniemi S.T., Henning M.A. (eds) Topics in Domination in Graphs. Developments in Mathematics, (2020) vol 64. Springer, Cham. https://doi.org/10.1007/978-3-030-51117-3-11
M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination. In: Haynes T.W., Hedetniemi S.T., Henning M.A. (eds) Structures of Domination in Graphs. Developments in Mathematics, (2021) vol 66. Springer, Cham. https://doi.org/10.1007/978-3-030-58892-2
M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination II, AKCE J. Graphs Combin. 17 (2020), 966–984.
M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination IV, AKCE J. Graphs Combin. (2025), 1–30. https://doi.org/10.1080/09728600.2025.2598772.
E.J. Cockayane, P.M. Dreyer Jr., S.M. Hedetniemi, and S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004), 11–22.
W.J. Desormeaux, T.W. Haynesa, and M.A. Henning, Bounds on the connected domination number of a graph, Discrete Appl. Math. 161 (2013), 2925–2931.
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
M.A. Henning and N. Jarfari Rad, On 2-Step and Hop Dominating Sets in Graphs, Graphs Combin. 33 (4) (2017), 913–927.
D.A. Mojdeh and A.S. Emadi, Hop domination polynomial of graphs, J. Discrete Math. Sci. Crypt. 23 (4), 825–840.
D.A. Mojdeh, G. Hao, I. Masoumi, and A. Parsian, Unique response strong Roman dominating functions of graphs, Electronic J. Graph Theory Appl. 9 (2) (2021), 469–484.
C. Natarajan and S.K. Ayyaswamy, Hop Domination in Graphs-II, An. Stt. Univ. Ovidius Constanta 23 (2) (2015), 187–199.
Y.M. Pabilona and H.M. Rara, Connected hop domination in graphs under some binary operations, Asian-European J. Math. 11 (2018), 1850075.
N. Jafari Rad and, A. Poureidi, On Hop Roman Domination in Trees, Comm. Combin. Optim. 4 (2019), 201–208.
N. Jafari Rad and E. Shabani, On the complexity of some hop domination parameters, Electronic J. Graph Theory Appl. 7 (1) (2019), 77–89.
E. Shabani, N. Jafari Rad, and A. Poureidi, Graphs with Large Hop Roman Domination Number, Computer Sci. J. Moldova 27 (2019), 3–22.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.