Bull. Korean Math. Soc. 2019; 56(1): 31-44
Online first article November 6, 2018 Printed January 31, 2019
https://doi.org/10.4134/BKMS.b180055
Copyright © The Korean Mathematical Society.
Xue-Gang Chen, Moo Young Sohn
North China Electric Power University; Changwon National University
A graph theoretical model called Roman domination in \linebreak graphs originates from the historical background that any undefended place (with no legions) of the Roman Empire must be protected by a stronger neighbor place (having two legions). It is applicable to military and commercial decision-making problems. A Roman dominating function for a graph $G = (V,E)$ is a function $f : V \to \{0, 1, 2 \}$ such that every vertex $v$ with $ f(v) = 0 $ has at least a neighbor $w$ in $G$ for which $f(w) = 2$. The Roman domination number of a graph is the minimum weight $ \sum_{v \in V} f(v)$ of a Roman dominating function. In order to deal a problem of a Roman domination-type defensive strategy under multiple simultaneous attacks, $\acute{A}$lvarez-Ruiz et al.~\cite{Ruiz} initiated the study of a new parameter related to Roman dominating function, which is called strong Roman domination. $\acute{A}$lvarez-Ruiz et al. posed the following problem: Characterize the graphs $G$ with equal strong Roman domination number and Roman domination number. In this paper, we construct a family of trees. We prove that for a tree, its strong Roman dominance number and Roman dominance number are equal if and only if the tree belongs to this family of trees.
Keywords: Roman domination number, strong Roman domination number, tree
MSC numbers: 05C69, 05C38
Supported by: This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education(2017R1D1A3B03029912).
2021; 58(1): 171-181
2015; 52(3): 955-962
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd