Trees with equal strong Roman domination number and Roman domination number
Bull. Korean Math. Soc. 2019 Vol. 56, No. 1, 31-44
Published online 2019 Jan 31
Xue-Gang Chen, Moo Young Sohn
North China Electric Power University; Changwon National University
Abstract : 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
Full-Text :


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail:   | Powered by, Ltd