آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 122 |
| تعداد مقالات | 1,559 |
| تعداد مشاهده مقاله | 1,666,882 |
| تعداد دریافت فایل اصل مقاله | 1,556,985 |
Efficient algorithms for independent Roman domination on some classes of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 10، دوره 8، شماره 1، خرداد 2023، صفحه 127-140 اصل مقاله (513.2 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2021.27305.1228 | ||
| نویسنده | ||
| Abolfazl Poureidi* | ||
| Shahrood University of Technology | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Independent Roman dominating function؛ Algorithm؛ Tree؛ Unicyclic graph؛ Proper interval graph | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 627 تعداد دریافت فایل اصل مقاله: 1,690 |
||