آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 112 |
| تعداد مقالات | 1,259 |
| تعداد مشاهده مقاله | 1,225,131 |
| تعداد دریافت فایل اصل مقاله | 1,085,079 |
Algorithmic Aspects of Quasi-Total Roman Domination in Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 10، دوره 7، شماره 1، شهریور 2022، صفحه 93-104 اصل مقاله (432.4 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2021.27126.1200 | ||
| نویسندگان | ||
| Venkata Subba Reddy P* 1؛ Mangal Vikas2 | ||
| 1National Institute of Technology Warangal | ||
| 2Department of Computer Science and Engineering, National Institute of Technology Warangal, India. | ||
| چکیده | ||
| For a simple, undirected, connected graph $G$($V,E$), a function $f : V(G) \rightarrow \lbrace 0, 1, 2 \rbrace$ which satisfies the following conditions is called a quasi-total Roman dominating function (QTRDF) of $G$ with weight $f(V(G))=\sum_{v \in V(G)} f(v)$. C1). Every vertex $u \in V(G)$ for which $f(u) = 0$ must be adjacent to at least one vertex $v$ with $f(v) = 2$, and C2). Every vertex $u \in V(G)$ for which $f(u) = 2$ must be adjacent to at least one vertex $v$ with $f(v) \geq 1$. For a graph $G$, the smallest possible weight of a QTRDF of $G$ denoted $\gamma_{qtR}(G)$ is known as the \textit{quasi-total Roman domination number} of $G$. The problem of determining $\gamma_{qtR}(G)$ of a graph $G$ is called minimum quasi-total Roman domination problem (MQTRDP). In this paper, we show that the problem of determining whether $G$ has a QTRDF of weight at most $l$ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. On the positive side, we show that MQTRDP for threshold graphs, chain graphs and bounded treewidth graphs is linear time solvable. Finally, an integer linear programming formulation for MQTRDP is presented. | ||
| کلیدواژهها | ||
| Domination number؛ quasi-total Roman domination؛ complexity classes؛ graph classes؛ linear programming | ||
| مراجع | ||
|
[1] A. Brandstädt, V.B. Le, and J.P. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, 1999.
[2] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[3] B. Courcelle, The monadic second-order logic of graphs. i. Recognizable sets of finite graphs, Inf. comput. 85 (1990), no. 1, 12–75.
[4] P.A. Dreyer, Applications and variations of domination in graphs, Ph.D. thesis, Rutgers University, New Jersey, 2000.
[5] O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009), no. 10, 3447–3451.
[6] S.C. Garc´ıa, A.C. Martínez, and I.G. Yero, Quasi-total Roman domination in graphs, Results Math. 74 (2019), no. 4, 1–18.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker Inc., 1998.
[8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, CRC press, 1998.
[9] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003), no. 1-3, 101–115.
[10] M.A. Henning and S.T. Hedetniemi, Defending the Roman Empire—A new strategy, Discrete Math. 266 (2003), no. 1-3, 239–251.
[11] Michael Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002), no. 2, 325–334.
[12] N. Jafari Rad and L. Volkmann, Roman domination perfect graphs, An. Stiint. Univ. Ovidius Constanta Ser. Mat. 19 (2011), 167–174.
[13] T. Kloks, M. Liedloff, J. Liu, and S.L. Peng, Roman domination in some special classes of graphs, Tech. report, TR-MA-04-01, 2004.
[14] M.-S. Lin and C.-M. Chen, Counting independent sets in tree convex bipartite graphs, Discrete Appl. Math. 218 (2017), 113–122.
[15] N.V.R. Mahadev and U.N. Peled, Threshold Graphs and Related Topics, Elsevier, 1995.
[16] C.S. ReVelle and K.E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[17] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[18] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, International symposium on algorithms and computation, Hong Kong, China, Springer, 2004, pp. 871–883.
[19] D.B. West, Introduction to Graph Theory, Second Edition, Prentice Hall, 2001.
[20] M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Alg. Disc. Meth. 3 (1982), no. 3, 351–358. | ||
|
آمار تعداد مشاهده مقاله: 501 تعداد دریافت فایل اصل مقاله: 514 |
||