تعداد نشریات | 5 |
تعداد شمارهها | 111 |
تعداد مقالات | 1,247 |
تعداد مشاهده مقاله | 1,199,533 |
تعداد دریافت فایل اصل مقاله | 1,060,236 |
Total $k$-Rainbow domination numbers in graphs | ||
Communications in Combinatorics and Optimization | ||
مقاله 3، دوره 3، شماره 1، شهریور 2018، صفحه 37-50 اصل مقاله (484.44 K) | ||
نوع مقاله: Original paper | ||
شناسه دیجیتال (DOI): 10.22049/cco.2018.25719.1021 | ||
نویسندگان | ||
Hossein Abdollahzadeh Ahangar* 1؛ Jafar Amjadi2؛ Nader Jafari Rad3؛ Vladimir D. Samodivkin4 | ||
1Babol Noshirvani University of Technology | ||
2Azarbaijan Shahid Madani University | ||
3Shahrood University of Technology | ||
4University of Architecture, Civil Engineering and Geodesy | ||
چکیده | ||
Let $k\geq 1$ be an integer, and let $G$ be a graph. A $k$-rainbow dominating function (or a {$k$-RDF) of $G$ is a function $f$ from the vertex set $V(G)$ to the family of all subsets of $\{1,2,\ldots ,k\}$ such that for every $v\in V(G)$ with $f(v)=\emptyset $, the condition $\bigcup_{u\in N_{G}(v)}f(u)=\{1,2,\ldots,k\}$ is fulfilled, where $N_{G}(v)$ is the open neighborhood of $v$. The weight of a $k$-RDF $f$ of $G$ is the value $\omega (f)=\sum _{v\in V(G)}|f(v)|$. A $k$-rainbow dominating function $f$ in a graph with no isolated vertex is called a total $k$-rainbow dominating function if the subgraph of $G$ induced by the set $\{v\in V(G) \mid f (v) \neq \emptyset\}$ has no isolated vertices. The total $k$-rainbow domination number of $G$, denoted by $\gamma_{trk}(G)$, is the minimum weight of a total $k$-rainbow dominating function on $G$. The total $1$-rainbow domination is the same as the total domination. In this paper we initiate the study of total $k$-rainbow domination number and we investigate its basic properties. In particular, we present some sharp bounds on the total $k$-rainbow domination number and we determine the total $k$-rainbow domination number of some classes of graphs. | ||
کلیدواژهها | ||
$k$-rainbow dominating function؛ $k$-rainbow domination number؛ total $k$-rainbow dominating function؛ total $k$-rainbow domination number | ||
مراجع | ||
[1] B. Brešar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. (2008), 213–225.
[2] B. Brešar and T.K. Sumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007), no. 17, 2394–2400.
[3] G.J. Chang, J. Wu, and X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010), no. 1, 8–12.
[4] M. Chellali and N. Jafari Rad, On 2-rainbow domination and Roman domination in graphs, Australas. J. Combin. 56 (2013), 85–93.
[5] N. Dehgardi, S.M. Sheikholeslami, and L. Volkmann, The rainbow domination subdivision numbers of graphs, Mat. Vesnik 67 (2015), no. 2, 102–114.
[6] M. Falahat, S.M. Sheikholeslami, and L. Volkmann, New bounds on the rainbow domination subdivision number, Filomat 28 (2014), no. 3, 615–622.
[7] T.W. Haynes, S. Hedetniemi, and P. Slater, Domination in Graphs: advanced topics, (1998).
[8] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[9] M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004), no. 1, 109–125.
[10] M.A. Henning, A survey of selected recent results on total domination in graphs, Discrete Math. 309 (2009), no. 1, 32–63.
[11] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013.
[12] V.R. Kulli and S.C. Sigarkanti, Inverse domination in graphs, Nat. Acad. Sci. Lett 14 (1991), no. 12, 473–475.
[13] D. Meierling, S.M. Sheikholeslami, and L. Volkmann, Nordhaus–Gaddum bounds on the k-rainbow domatic number of a graph, Appl. Math. Lett. 24 (2011), no. 10, 1758–1761.
[14] O. Ore, Theory of Graphs, vol. 38, American Mathematical Society Providence, RI, 1962.
[15] Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavlić, and J. Žerovnik, On rainbow domination numbers of graphs, Inform. Sci. 254 (2014), 225–234.
[16] S.M. Sheikholeslami and L. Volkmann, The k-rainbow domatic number of a graph, Discuss. Math. Graph Theory 32 (2012), no. 1, 129–140.
[17] C. Tong, X. Lin, Y. Yang, and M. Luo, 2-rainbow domination of generalized Petersen graphs p(n, 2), Discrete Appl. Math. 157 (2009), no. 8, 1932–1937.
[18] Y. Wu and N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs Combin. (2013), 1–9.
[19] Y. Wu and H. Xing, Note on 2-rainbow domination and Roman domination in graphs, Appl. Math. Lett. 23 (2010), no. 6, 706–709.
[20] G. Xu, 2-rainbow domination in generalized Petersen graphs p(n, 3), Discrete Appl. Math. 157 (2009), no. 11, 2570–2573. | ||
آمار تعداد مشاهده مقاله: 1,571 تعداد دریافت فایل اصل مقاله: 1,948 |