آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 118 |
| تعداد مقالات | 1,485 |
| تعداد مشاهده مقاله | 1,600,911 |
| تعداد دریافت فایل اصل مقاله | 1,497,004 |
Algorithmic Results on Independent Roman {2}-Domination | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 17، دوره 11، شماره 2، شهریور 2026، صفحه 599-627 اصل مقاله (1.46 M) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.29156.1872 | ||
| نویسندگان | ||
| Qiyun Liu1؛ Yonghao Song1؛ Zehui Shao1؛ Huiqin Jiang* 1، 2 | ||
| 1Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China | ||
| 2School of Computer Science of Information Technology, Qiannan Normal University for Nationalities, Duyun 558000, China | ||
| چکیده | ||
| An independent Roman $\{2\}$-dominating function (IR2DF) $f:V \rightarrow \{0, 1, 2\}$ in a graph $G=(V,E)$ has the properties that $\sum_{u\in N(v)}f(u) \geq 2$ if $f(v)=0$, and $f(u)=0$ for $u \in N(v)$ if $f(v) \geq 1$, where $v \in V$. The weight of an IR2DF in a graph $G$ is defined as the sum of its function values for all vertices, given by $\omega(f)=\sum_{v\in V}f(v)$. The independent Roman $\{2\}$-domination number of $G$, denoted $i_{\{R2\}}(G)$, is the minimum weight of all IR2DFs in $G$. In this paper, we prove that the independent Roman $\{2\}$-domination problem (IR2D) is NP-complete, even when restricted to chordal bipartite graphs. We then give an exact formula for the IR2D in corona graphs. Finally, we present two linear-time algorithms for solving IR2D for proper interval graphs and block-cactus graphs, respectively. | ||
| کلیدواژهها | ||
| independent Roman {2}-domination؛ linear-time algorithm؛ NP-completeness؛ proper interval graph؛ block-cactus graph | ||
| مراجع | ||
|
[1] A.V. Aho and J.E. Hopcroft, The design and analysis of computer algorithms, Pearson Education India, 1974.
[2] R.B. Allan and R. Laskar, On domination and independent domination numbers of a graph, Discrete Math. 23 (1978), no. 2, 73–76. https://doi.org/10.1016/0012-365X(78)90105-X
[3] J.A. Bondy and U.S.R. Murty, Graph theory, Springer Publishing Company, Incorporated, 2008.
[4] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A.A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016), 22–28. https://doi.org/10.1016/j.dam.2015.11.013
[5] M. Chellali, N. Jafari Rad, S.M. Sheikholeslami, and L. Volkmann, Varieties of Roman domination, Structures of Domination in Graphs (T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, eds.), Springer International Publishing, Cham, 2021, pp. 273–307. [6] M. Chellali and A. Rahmouni, Independent Roman $\{2\}$-domination in graphs, Discrete Appl. Math. 236 (2018), 408–414. https://doi.org/10.1016/j.dam.2017.10.028
[7] H. Chen and C. Lu, Roman {2}-domination problem in graphs., Discuss. Math. Graph Theory 42 (2022), no. 2. 641–660. https://doi.org/10.7151/dmgt.2332
[8] E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22. https://doi.org/10.1016/j.disc.2003.06.004
[9] R. Frucht and F. Harary, On the corona of two graphs, (1970).
[10] M.C. Golumbic, Algorithmic graph theory and perfect graphs, Elsevier, 2004.
[11] M.C. Golumbic and C.F. Goss, Perfect elimination and chordal bipartite graphs, J. Graph Theory 2 (1978), no. 2, 155–163. https://doi.org/10.1002/jgt.3190020209
[12] F. Harary, A characterization of block-graphs, Canad. Math. Bull. 6 (1963), no. 1, 1–6.
[13] S.T. Hedetniemi, R. Laskar, and J. Pfaff, A linear algorithm for finding a minimum dominating set in a cactus, Discrete Appl. Math. 13 (1986), no. 2-3, 287–292. https://doi.org/10.1016/0166-218X(86)90089-2
[14] W.K. Hon, C.S. Liu, S.L. Peng, and C.Y. Tang, Power domination on block-cactus graphs, The 24th Workshop on Combinatorial Mathematics and Computation Theory, 2007, pp. 280–284.
[15] R.E. Jamison and R. Laskar, Elimination orderings of chordal graphs, Comb. Appl. (1982), 192–200.
[16] B. Li and W. Shang, Independent Roman {2}-domination in trees, Chinese Quart. J. Math. 37 (2022), no. 4, 386–393. https://doi.org/10.13371/j.cnki.chin.q.j.m.2022.04.006
[17] M. Liedloff, T. Kloks, J. Liu, and S.L. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008), no. 18, 3400–3415. https://doi.org/10.1016/j.dam.2008.01.011
[18] T.A. McKee and F.R. McMorris, Topics in intersection graph theory, SIAM, 1999.
[19] H. Müller and A. Brandstädt, The NP-completeness of steiner tree and dominating set for chordal bipartite graphs, Theor. Comput. Sci. 53 (1987), no. 2-3, 257–265. https://doi.org/10.1016/0304-3975(87)90067-3
[20] O. Ore, Theory of graphs, Colloquium Publications, American Mathematical Society, 1962.
[21] C. Padamutham and V.S.R. Palagiri, Complexity aspects of variants of independent Roman domination in graphs, Bull. Iranian Math. Soc. 47 (2021), 1715–1735. https://doi.org/10.1007/s41980-020-00468-5
[22] B.S. Panda and S.K. Das, A linear time recognition algorithm for proper interval graphs, Inform. Process. Lett. 87 (2003), no. 3, 153–161. https://doi.org/10.1016/S0020-0190(03)00298-9
[23] A. Poureidi and N. Jafari Rad, Algorithmic aspects of the independent 2-rainbow domination number and independent Roman {2}-domination number, Discuss. Math. Graph Theory 42 (2020), 709–726. https://doi.org/10.7151/dmgt.2299
[24] D. Rautenbach and L. Volkmann, The domatic number of block-cactus graphs, Discrete Math. 187 (1998), no. 1-3, 185–193. https://doi.org/10.1016/S0012-365X(97)00234-3
[25] I. Stewart, Defend the Roman empire!, Sci. Am. 281 (1999), no. 6, 136–138.
[26] D. Wei and C. Lu, Independent double Roman domination on block graphs, arXiv preprint arXiv:1908.00784 (2019).
[27] D.B. West, Introduction to Graph Theory, vol. 2, Prentice hall Upper Saddle River, 2001.
[28] 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), no. 2, 389–400. https://doi.org/10.1051/ro/2018116 | ||
|
آمار تعداد مشاهده مقاله: 321 تعداد دریافت فایل اصل مقاله: 244 |
||