Total $k$-Rainbow domination numbers in graphs

Document Type : Original paper

Authors

1 Babol Noshirvani University of Technology

2 Azarbaijan Shahid Madani University

3 Shahrood University of Technology

4 University of Architecture, Civil Engineering and Geodesy

Abstract

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. 

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization
Volume 3, Issue 1
June 2018
Pages 37-50

Files

Share

How to cite

Statistics