TY - JOUR
ID - 2058
TI - ALGORITHMIC ASPECTS OF ROMAN GRAPHS
JO - Journal of Algebraic Systems
JA - JAS
LA - en
SN - 2345-5128
AU - Poureidi, A.
AD - Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood,
Iran.
Y1 - 2021
PY - 2021
VL - 9
IS - 1
SP - 119
EP - 135
KW - Dominating set
KW - Roman dominating function
KW - Algorithm
KW - 3-SAT Problem
KW - unicyclic graph
DO - 10.22044/jas.2020.8188.1400
N2 - Let $G=(V, E)$ be a graph. A set $S \subseteq V$ is called a dominating set of $G$ if for every $v\in V-S$ there is at least one vertex $u \in N(v)$ such that $u\in S$. The domination number of $G$, denoted by $\gamma(G)$, is equal to the minimum cardinality of a dominating set in $G$. A Roman dominating function (RDF) on $G$ is a function $f:V\longrightarrow\{0,1,2\}$ such that every vertex $v\in V$ with $f(v)=0$ is adjacent to at least one vertex $u$ with $f(u)=2$. The weight of $f$ is the sum $f(V)=\sum_{v\in V}f (v)$. The minimum weight of a RDF on $G$ is the Roman domination number of $G$, denoted by $\gamma_R(G)$. A graph $G$ is a Roman Graph if $\gamma_R(G)=2\gamma(G)$. In this paper, we first study the complexity issue of the problem posed in [E.J. Cockayane, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, On Roman domination in graphs, \textit{Discrete Math.} 278 (2004), 11--22], and show that the problem of deciding whether a given graph is a Roman graph is NP-hard even when restricted to chordal graphs. Then, we give linear algorithms that compute the domination number and the Roman domination number of a given unicyclic graph. Finally, using these algorithms we give a linear algorithm that decides whether a given unicyclic graph is a Roman graph.
UR - https://jas.shahroodut.ac.ir/article_2058.html
L1 - https://jas.shahroodut.ac.ir/article_2058_3654a9bd6949d46a357a1413df58873e.pdf
ER -