Algorithmic Results on Independent Roman {2}-Domination

Articles in Press

Document Type : Original paper

Authors

1 Institute of Computing Science and Technology,Guangzhou University, Guangzhou 510006, China

2 Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China

3 School of Computer Science of Information Technology, Qiannan Normal University for Nationalities, Duyun 558000, China

Abstract

An independent Roman {2}-dominating function (IR2DF) f:V→{0,1,2} in a graph G=(V,E) has the properties that ∑u∈N(v)f(u)≥2 if f(v)=0, and f(u)=0 for u∈N(v) if f(v)≥1, where v∈V. The weight of an IR2DF in a graph G is defined as the sum of its function values for all vertices, given by ω(f)=∑v∈Vf(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.

Keywords

Main Subjects

References

[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
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 31 August 2024

Files

Share

How to cite

Statistics