PDF
Discussiones Mathematicae Graph Theory 32(1) (2012)
129-140
DOI: https://doi.org/10.7151/dmgt.1591
The k-rainbow Domatic Number of a Graph
Seyyed Mahmoud Sheikholeslami
Department of Mathematics | Lutz Volkmann
Lehrstuhl II für Mathematik |
Abstract
For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set {1,2, …,k} such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ∪u ∈ N(v)f(u) = {1,2, …,k} is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set {f1,f2, …,fd} of k-rainbow dominating functions on G with the property that ∑i = 1d |fi(v) | ≤ k for each v ∈ V(G), is called a k-rainbow dominating family (of functions) on G. The maximum number of functions in a k-rainbow dominating family on G is the k-rainbow domatic number of G, denoted by drk(G). Note that dr1(G) is the classical domatic number d(G). In this paper we initiate the study of the k-rainbow domatic number in graphs and we present some bounds for drk(G). Many of the known bounds of d(G) are immediate consequences of our results.
Keywords: k-rainbow dominating function, k-rainbow domination number, k-rainbow domatic number
2010 Mathematics Subject Classification: 05C69.
References
[1] | C. Berge, Theory of Graphs and its Applications (Methuen, London, 1962). |
[2] | B. Brešar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213--225. |
[3] | B. Brešar and T.K. Šumenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math. 155 (2007) 2394--2400, doi: 10.1016/j.dam.2007.07.018. |
[4] | G.J. Chang, J. Wu and X. Zhu, Rainbow domination on trees, Discrete Appl. Math. 158 (2010) 8--12, doi: 10.1016/j.dam.2009.08.010. |
[5] | T. Chunling, L. Xiaohui, Y. Yuansheng and L. Meiqin, 2-rainbow domination of generalized Petersen graphs P(n,2), Discrete Appl. Math 157 (2009) 1932--1937, doi: 10.1016/j.dam.2009.01.020. |
[6] | E.J. Cockayne, P.J.P. Grobler, W.R. Gründlingh, J. Munganga and J.H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19--32. |
[7] | E.J. Cockayne and S.T. Hedetniemi, Towards a theory of domination in graphs, Networks 7 (1977) 247--261, doi: 10.1002/net.3230070305. |
[8] | B. Hartnell and D.F. Rall, On dominating the Cartesian product of a graph and K2, Discuss. Math. Graph Theory 24 (2004) 389--402, doi: 10.7151/dmgt.1238. |
[9] | T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). |
[10] | H.B. Walikar, B.D. Acharya and E. Sampathkumar, Recent Developments in the Theory of Domination in Graphs (in: MRI Lecture Notes in Math., Mahta Research Instit., Allahabad, 1979). |
[11] | D. B. West, Introduction to Graph Theory (Prentice-Hall, Inc, 2000). |
[12] | G. Xu, 2-rainbow domination of generalized Petersen graphs P(n,3), Discrete Appl. Math. 157 (2009) 2570--2573, doi: 10.1016/j.dam.2009.03.016. |
Received 10 September 2010
Revised 10 March 2011
Accepted 15 March 2011
Close