Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

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.

Trees with equal strong Roman domination number and Roman domination number

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

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

Stats or Metrics

Share this article on :

Related articles in BKMS

more +