ALGORITHMIC ASPECTS OF ROMAN GRAPHS | ||
| Journal of Algebraic Systems | ||
| دوره 9، شماره 1، آذر 2021، صفحه 119-135 اصل مقاله (207.87 K) | ||
| نوع مقاله: Original Manuscript | ||
| شناسه دیجیتال (DOI): 10.22044/jas.2020.8188.1400 | ||
| نویسنده | ||
| A. Poureidi* | ||
| Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran. | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Dominating set؛ Roman dominating function؛ Algorithm؛ 3-SAT Problem؛ unicyclic graph | ||
| مراجع | ||
|
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. | ||
|
آمار تعداد مشاهده مقاله: 417 تعداد دریافت فایل اصل مقاله: 406 |
||