ALGORITHMIC ASPECTS OF ROMAN GRAPHS

Document Type : Original Manuscript

Author

Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran.

Abstract

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.

Keywords

References

1. H. Abdollahzadeh Ahangar, M. Chellali, S. M. Sheikholeslami, On the Roman domination in graphs, Discrete Appl. Math., 232 (2017), 1–7.

2. R. A. Beeler, T. W. Haynesa and S. T. Hedetniemi, Double Roman domination, Discrete Appl. Math., 211 (2016), 23–29.

3. M. Chellali, T. W. Haynes, S. T. Hedetniemi, A. MacRae, Roman f2g-domination, Discrete Appl. Math., 204 (2016), 22–28.

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

5. N. Jafari Rad and H. Rahbani, Some progress on the Roman domination in graphs, Discuss. Math. Graph Theory, 39 (2019), 41–53.

6. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.

7. T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination
in Graphs, Marcel Dekker, In c., New York, 1998.

8. M. A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory, 22 (2002), 325–334.

9. M. Liedloff, T. Kloks, J. Liu and S.-L. Pen, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math., 156 (2008), 3400– 3415.

10. C. S. Revelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), 585–594.
11. I. Stewart, Defend the roman empire!, Sci. Amer., 281 (1999), 136–139.

12. J. Yue, M. Wei, M. Li and G. Liu, On the Roman domination of graphs, Appl. Math. Comput., 338 (2018), 669–675.

13. X. Zhang, Z. Li, H. Jiang and Z. Shao, Double Roman domination in trees, Inform. Process. Lett., 134 (2018), 31–34.
Journal of Algebraic Systems
Volume 9, Issue 1
September 2021
Pages 119-135

Files

Share

How to cite

Statistics