Algorithmic Results on Independent Roman {2}-Domination

Liu, Qiyun; Song, Yonghao; Shao, Zehui; Jiang, Huiqin

doi:10.22049/cco.2024.29156.1872

تعداد نشریات	5
تعداد شماره‌ها	116
تعداد مقالات	1,355
تعداد مشاهده مقاله	1,361,275
تعداد دریافت فایل اصل مقاله	1,313,786

	Algorithmic Results on Independent Roman {2}-Domination
Communications in Combinatorics and Optimization
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 10 شهریور 1403 اصل مقاله (1.46 M)
نوع مقاله: Original paper
شناسه دیجیتال (DOI): 10.22049/cco.2024.29156.1872
نویسندگان
Qiyun Liu¹؛ Yonghao Song¹؛ Zehui Shao¹؛ Huiqin Jiang^* ²^{، 3}
¹Institute of Computing Science and Technology,Guangzhou University, Guangzhou 510006, China
²Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China
³School 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
آمار تعداد مشاهده مقاله: 196 تعداد دریافت فایل اصل مقاله: 123

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

آمار

Algorithmic Results on Independent Roman {2}-Domination