آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 111 |
| تعداد مقالات | 1,247 |
| تعداد مشاهده مقاله | 1,199,552 |
| تعداد دریافت فایل اصل مقاله | 1,060,263 |
Double Roman domination in graphs: algorithmic complexity | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 5، دوره 8، شماره 3، آذر 2023، صفحه 491-503 اصل مقاله (613.96 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2022.27661.1309 | ||
| نویسنده | ||
| Abolfazl Poureidi* | ||
| Shahrood University of Technology | ||
| چکیده | ||
| Let $G=(V,E)$ be a graph. A double Roman dominating function (DRDF) of $G $ is a function $f:V\to \{0,1,2,3\}$ such that, for each $v\in V$ with $f(v)=0$, there is a vertex $u $ adjacent to $v$ with $f(u)=3$ or there are vertices $x$ and $y $ adjacent to $v$ such that $f(x)=f(y)=2$ and for each $v\in V$ with $f(v)=1$, there is a vertex $u $ adjacent to $v$ with $f(u)>1$. The weight of a DRDF $f$ is $ f (V) =\sum_{ v\in V} f (v)$. Let $n$ and $k$ be integers such that $3\leq 2k+ 1 \leq n$. The generalized Petersen graph $GP (n, k)=(V,E) $ is the graph with $V=\{u_1, u_2,\ldots, u_n\}\cup\{v_1, v_2,\ldots, v_n\}$ and $E=\{u_iu_{i+1}, u_iv_i, v_iv_{i+k}: 1 \leq i \leq n\}$, where addition is taken modulo $n$. In this paper, we firstly prove that the decision problem associated with double Roman domination is NP-omplete even restricted to planar bipartite graphs with maximum degree at most 4. Next, we give a dynamic programming algorithm for computing a minimum DRDF (i.e., a DRDF with minimum weight along all DRDFs) of $GP(n,k )$ in $O(n81^k)$ time and space and so a minimum DRDF of $GP(n,O(1))$ can be computed in $O( n)$ time and space. | ||
| کلیدواژهها | ||
| Double Roman dominating function؛ Algorithm؛ Dynamic programming؛ Generalized Petersen graph | ||
| مراجع | ||
|
[1] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, On the double Roman domination in graphs, Discrete Appl. Math. 232 (2017), 1–7.
[2] H. Abdollahzadeh Ahangar, M. Chellali, and S.M. Sheikholeslami, Outer independent double Roman domination, Appl. Math. Comput. 364 (2020), ID: 124617.
[3] H. Abdollahzadeh Ahangar, M. Chellali, S.M. Sheikholeslami, and J.C. Valenzuela-Tripodoro, Maximal double Roman domination in graphs, Appl. Math. Comput. 414 (2022), ID: 126662.
[4] S. Banerjee, M.A. Henning, and D. Pradhan, Algorithmic results on double Roman domination in graphs, J. Comb. Optim. 39 (2020), no. 1, 90–114.
[5] R.A. Beeler, T.W. Haynes, and S.T. Hedetniemi, Double Roman domination, Discrete Appl. Math. 211 (2016), 23–29.
[6] G. Hao, L. Volkmann, and D.A. Mojdeh, Total double Roman domination in graphs, Commun. Comb. Optim. 5 (2020), no. 1, 27–39.
[7] N. Jafari Rad and H. Rahbani, Some progress on the double Roman domination in graphs, Discuss. Math. Graph Theory 39 (2019), no. 1.
[8] R. Khoeilar, H. Karami, M. Chellali, and S.M. Sheikholeslami, An improved upper bound on the double Roman domination number of graphs with minimum degree at least two, Discrete Appl. Math. 270 (2019), 159–167.
[9] S. Kosari, Z. Shao, S.M. Sheikholeslami, M. Chellali, R. Khoeilar, and H. Karami, Double Roman domination in graphs with minimum degree at least two and no c5-cycle, Graphs Combin. 38 (2022), no. 2, 1–16.
[10] Bojan Mohar, Face covers and the genus problem for apex graphs, J. Combin. Theory Ser. B 82 (2001), no. 1, 102–117.
[11] 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), no. 3, 1081–1086.
[12] A. Poureidi and N. Jafari Rad, On algorithmic complexity of double Roman domination, Discrete Appl. Math. 285 (2020), 539–551.
[13] L. Volkmann, Double Roman domination and domatic numbers of graphs, Commun. Comb. Optim. 3 (2018), no. 1, 71–77.
[14] M.E. Watkins, A theorem on Tait colorings with an application to the generalized Petersen graphs, J. Combin. Theory 6 (1969), no. 2, 152–164.
[15] X. Zhang, Z. Li, H. Jiang, and Z. Shao, Double Roman domination in trees, Inform. Process. Lett. 134 (2018), 31–34. | ||
|
آمار تعداد مشاهده مقاله: 460 تعداد دریافت فایل اصل مقاله: 975 |
||