آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 116 |
| تعداد مقالات | 1,347 |
| تعداد مشاهده مقاله | 1,351,511 |
| تعداد دریافت فایل اصل مقاله | 1,292,517 |
Algorithmic complexity of triple Roman dominating functions on graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 4، دوره 9، شماره 2، شهریور 2024، صفحه 217-232 اصل مقاله (809.44 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2023.27884.1385 | ||
| نویسندگان | ||
| Abolfazl Poureidi* ؛ Jafar Fathali | ||
| Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran | ||
| چکیده | ||
| Given a graph $G=(V,E)$, a function $f:V\to \{0,1,2,3,4\}$ is a triple Roman dominating function (TRDF) of $G$, for each vertex $v\in V$, (i) if $f (v ) = 0 $, then $v$ must have either one neighbour in $V_4$, or either two neighbours in $V_2 \cup V_3$ (one neighbour in $V_3$) or either three neighbours in $V_2 $, (ii) if $f (v ) = 1 $, then $v$ must have either one neighbour in $V_3 \cup V_4$ or either two neighbours in $V_2 $, and if $f (v ) = 2 $, then $v$ must have one neighbour in $V_2 \cup V_3\cup V_4$. The triple Roman domination number of $G$ is the minimum weight of an TRDF $f$ of $G$, where the weight of $f$ is $\sum_{v\in V}f(v)$. The triple Roman domination problem is to compute the triple Roman domination number of a given graph. In this paper, we study the triple Roman domination problem. We show that the problem is NP-complete for the star convex bipartite and the comb convex bipartite graphs and is APX-complete for graphs of degree at~most~4. We propose a linear-time algorithm for computing the triple Roman domination number of proper interval graphs. We also give an $( 2 H(\Delta(G)+1) -1 )$-approximation algorithm for solving the problem for any graph $G$, where $ \Delta(G)$ is the maximum degree of $G$ and $H(d)$ denotes the first $d$ terms of the harmonic series. In addition, we prove that for any $\varepsilon>0$ there is no $(1/4-\varepsilon)\ln|V|$-approximation polynomial-time algorithm for solving the problem on bipartite and split graphs, unless NP $\subseteq$ DTIME $(|V|^{O(\log\log|V |)})$. | ||
| کلیدواژهها | ||
| Triple Roman domination؛ Approximation algorithm؛ NP-complete؛ Proper interval graph؛ APX-complete | ||
| مراجع | ||
|
[1] H. Abdollahzadeh Ahangar, M.P. ´Alvarez, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Triple Roman domination in graphs, Applied Math. Comput. 391 (2021), Article ID: 125444. https://doi.org/10.1016/j.amc.2020.125444
[2] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Total Roman {2}-ominating functions in graphs, Discuss. Math. Graph Theory 42 (2022), no. 3, 937–958. https://doi.org/10.7151/dmgt.2316
[3] P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs, Theoretical Comput. Sci. 237 (2000), no. 1-2, 123–134. https://doi.org/10.1016/S0304-3975(98)00158-3
[4] J. Amjadi and H. Sadeghi, Triple Roman domination subdivision number in graphs., Comput. Sci. J. Moldova 30 (2022), no. 1, 109–130.
[5] T. Araki and H. Miyazaki, Secure domination in proper interval graphs, Discrete Appl. Math. 247 (2018), 70–76. https://doi.org/10.1016/j.dam.2018.03.040
[6] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29. https://doi.org/10.1016/j.dam.2016.03.017
[7] K.S. Booth and G.S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci. 13 (1976), no. 3, 335–379. https://doi.org/10.1016/S0022-0000(76)80045-1
[8] M. Chlebík and J. Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs, Inform. Comput. 206 (2008), no. 11, 1264–1275. https://doi.org/10.1016/j.ic.2008.07.003
[9] M. Hajjari, H. Abdollahzadeh Ahangar, R. Khoeilar, Z. Shao, and S.M. Sheikholeslami, New bounds on the triple Roman domination number of graphs, J. Math. 2022 (2022), Artice ID: 9992618. https://doi.org/10.1155/2022/9992618
[10] M. Hajjari, H. Abdollahzadeh Ahangar, R. Khoeilar, Z. Shao, and S.M. Sheikholeslami, An upper bound on triple Roman domination, Commun. Comb. Optim. 8 (2023), no. 3, 505–511. https://doi.org/10.22049/cco.2022.27816.1359
[11] D.S. Johnson and M.R. Garey, Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman, New York, 1979.
[12] M.S. Lin and C.M. Chen, Counting independent sets in tree convex bipartite graphs, Discrete Appl. Math. 218 (2017), 113–122. https://doi.org/10.1016/j.dam.2016.08.017
[13] P.J. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl. 25 (1993), no. 7, 15–25. https://doi.org/10.1016/0898-1221(93)90308-I
[14] F. Nahani Pour, H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Global triple Roman dominating function, Discrete Appl. Math. 314 (2022), 228–237. https://doi.org/10.1016/j.dam.2022.02.015
[15] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. System Sci. 43 (1991), no. 3, 425–440. https://doi.org/10.1016/0022-0000(91)90023-X
[16] A. Poureidi, Double Roman domination in graphs: algorithmic complexity, Commun. Comb. Optim. 8 (2023), no. 3, 491–503. https://doi.org/10.22049/cco.2022.27661.1309
[17] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), no. 1, 71–77. https://doi.org/10.22049/cco.2018.26125.1078 | ||
|
آمار تعداد مشاهده مقاله: 568 تعداد دریافت فایل اصل مقاله: 1,508 |
||