Efficient algorithms for independent Roman domination on some classes of graphs

Document Type : Original paper

Author

Shahrood University of Technology

Abstract

Let $G=(V,E)$ be a given graph of order $n $. A function $f : V \to \{0,1, 2\}$ is an independent Roman dominating function (IRDF) on $G$ if for every vertex $v\in V$ with $f(v)=0$ there is a vertex $u$ adjacent to $v$ with $f(u)=2$ and $\{v\in V:f(v)> 0\}$ is an independent set. The weight of an IRDF $f$ on $G $ is the value $f(V)=\sum_{v\in V}f(v)$. The minimum weight of an IRDF among all IRDFs on $G$ is called the independent Roman domination number of~$G$. In this paper, we give algorithms for computing the independent Roman domination number of $G$ in $O(|V|)$ time when $G=(V,E)$ is a tree, unicyclic graph or proper interval graph.

Keywords

Main Subjects

References

[1] T. Araki and H. Miyazaki, Secure domination in proper interval graphs, Discrete Appl. Math. 247 (2018), 70–76.
[2] F. Azvin, N. Jafari Rad, and L. Volkmann, Bounds on the outer-independent double Italian domination number, Commun. Comb. Optim. 6 (2021), no. 1, 123–136.
[3] 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.
[4] M. Cary, J. Cary, and S. Prabhu, Independent domination in directed graphs, Commun. Comb. Optim. 6 (2021), no. 1, 67–80.
[5] P. Chakradhar and P. Venkata Subba Reddy, Complexity aspects of variants of independent Roman domination in graphs, Bull. Iran. Math. Soc. 47 (2021), no. 6, 1715–1735.
6] M. Chellali and N. Jafari Rad, Strong equality between the Roman domination and independent Roman domination numbers in trees., Discuss. Math. Graph Theory 33 (2013), no. 2, 246–256.
[7] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[8] N. Dehgardi and M. Chellali, Outer independent Roman domination number of trees, Commun. Comb. Optim. 6 (2021), no. 2, 273–286.
[9] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619.
[10] P.J. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Comput. Math. Appl. 25 (1993), no. 7, 15–25.
[11] A.S. Pedersen and P.D. Vestergaard, The number of independent sets in unicyclic graphs, Discrete Appl. Math. 152 (2005), no. 1-3, 246–256.
[12] S.M. Sheikholeslami and S. Nazari-Moghaddam, On trees with equal Roman domination and outer-independent Roman domination numbers, Commun. Comb. Optim. 4 (2019), no. 2, 185–199.
[13] M. Targhi, N. Jafari Rad, and M.S. Moradi, Properties of independent Roman domination in graphs, Australas. J. Combin. 52 (2012), 11–18.
Communications in Combinatorics and Optimization
Volume 8, Issue 1
March 2023
Pages 127-140

Files

Share

How to cite

Statistics