پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,706 |
| تعداد مقالات | 13,973 |
| تعداد مشاهده مقاله | 33,628,765 |
| تعداد دریافت فایل اصل مقاله | 13,339,560 |
Independent roman $\{3\}$-domination | ||
| Transactions on Combinatorics | ||
| دوره 11، شماره 2، شهریور 2022، صفحه 99-110 اصل مقاله (354 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2021.127953.1840 | ||
| نویسندگان | ||
| P. Chakradhar* 1؛ P. Venkata Subba Reddy2 | ||
| 1Department of Computer Science and Engineering, SR University, Warangal - 506 371, India | ||
| 2Department of Computer Science and Engineering, National Institute of Technology, Warangal - 506 004, India | ||
| چکیده | ||
| Let $G$ be a simple, undirected graph. In this paper, we initiate the study of independent Roman $\{3\}$-domination. A function $g : V(G) \rightarrow \lbrace 0, 1, 2, 3 \rbrace$ having the property that $\sum_{v \in N_G(u)}^{} g(v) \geq 3$, if $g(u) = 0$, and $\sum_{v \in N_G(u)}^{} g(v) \geq 2$, if $g(u) = 1$ for any vertex $u \in V(G)$, where $N_G(u)$ is the set of vertices adjacent to $u$ in $G$, and no two vertices assigned positive values are adjacent is called an \textit{ independent Roman $\{3\}$-dominating function} (IR3DF) of $G$. The weight of an IR3DF $g$ is the sum $g(V) = \sum_{v \in V}g(v)$. Given a graph $G$ and a positive integer $k$, the independent Roman $\{3\}$-domination problem (IR3DP) is to check whether $G$ has an IR3DF of weight at most $k$. We investigate the complexity of IR3DP in bipartite and chordal graphs. The minimum independent Roman $\lbrace 3 \rbrace$-domination problem (MIR3DP) is to find an IR3DF of minimum weight in the input graph. We show that MIR3DP is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs. We also show that the domination problem and IR3DP are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MIR3DP. | ||
| کلیدواژهها | ||
| Roman {3}-domination؛ Independent Roman {3}-domination؛ NP-complete؛ APX-hard؛ Integer linear programming | ||
| مراجع | ||
|
[1] A. Rahmouni and M. Chellali, Independent Roman {2}-domination in graphs, Discrete Appl. Math., 236 (2018) 408–414. [2] B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput., 85 (1990) 12–75. [3] C. E. Leiserson, R. L. Rivest, T. H. Cormen and C. Stein, Introduction to algorithms, Second edition. MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001. [4] C. S. ReVelle and K. E. Rosing, Defendens imperium romanum: a classical problem in military strategy, Amer. Math. Monthly, 107 (2000) 585–594. [5] C. Padamutham and V. S. R. Palagiri, Complexity Aspects of Variants of Independent Roman Domination in Graphs, Bull. Iranian Math. Soc., (2021) 1715–1735. [6] C. Padamutham and V. S. R. Palagiri, Algorithmic aspects of Roman domination in graphs, J. Appl. Math. Comput., 64 (2020) 89–102. [7] C. Padamutham and V. S. R. Palagiri, Complexity of Roman {2}-domination and the double Roman domination in graphs, AKCE Int. J. Graphs Comb., 17 (2020) 1081–1086. [8] D. A. Mojdeh and L. Volkmann, Roman {3}-domination (double Italian domination), Discrete Appl. Math., 283 (2020) 555–564. [9] D. B. West, Introduction to Graph Theory, 2, Upper Saddle River: Prentice Hall, 2001.
[10] E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math., 278 (2004) 11–22. [11] F. Alizade, H. R. Maimani, L. P. Majd and M. R. Parsa, Roman {2}-domination in graphs and graph products, (2017). [12] M. Adabi, E. E. Targhi, N. J. Rad and M. S. Moradi, Properties of independent Roman domination in graphs, Australas. J. Combin., 52 (2012) 11–18. [13] M. Chellali and N. J. Rad, Strong equality between the Roman domination and independent Roman domination numbers in trees, Discuss. Math. Graph T., 33 (2013) 337–346. [14] M. Chlebik and J. Chlebı́ková, The complexity of combinatorial optimization problems on d-dimensional boxes, SIAM J. Discret. Math., 21 (2007) 158–169. [15] M. Ivanović, Improved mixed integer linear programing formulations for roman domination problem, Publ. de l’Institut Math., 99 (2016) 51–58. [16] M. Chellali, T. W. Haynes, S. T. Hedetniemi and A. A. McRae, Roman {2}-domination, Discrete Appl. Math., 204 (2016) 22–28. [17] M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. [18] M. Yannakakis, Node- and edge-deletion NP-complete problems, In Proceedings of the Tenth Annual ACM Sympo- sium on Theory of Computing, STOC, New York, USA, (1978) 253–264. [19] N. Jafari Rad and L. Volkmann, Roman domination perfect graphs, An. Stiint. Univ. Ovidius Constanta Ser. Mat., 19 (2011) 167–174. [20] N. Mahadev and U. Peled, Threshold graphs and related topics, Annals of Discrete Mathematics, 56, North-Holland Publishing Co., Amsterdam, 1995. [21] O. Favaron, H. Karami, R. Khoeilar and S. M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math., 309 (2009) 3447–3451. [22] P. Wu, Z. Li, Z. Shao and S. M. Sheikholeslami, Trees with equal Roman {2}-domination number and independent Roman {2}-domination number, RAIRO-Oper. Res., 53 (2019) 389–400. [23] R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, Algorithms and computation, Lecture Notes in Comput. Sci., Springer, Berlin, (2004) 871–883. [24] T. W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of domination in graphs, Monographs and Textbooks in Pure and Applied Mathematics, 208, Marcel Dekker, Inc., New York, 1998. [25] T. W. Haynes, S. Hedetniemi and P. Slater, Domination in graphs: advanced topics, Marcel Dekker, 1997. | ||
|
آمار تعداد مشاهده مقاله: 820 تعداد دریافت فایل اصل مقاله: 1,038 |
||