The k-rainbow domatic number of a graph

Seyyed Mahmoud Sheikholeslami; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 1, page 129-140
  • ISSN: 2083-5892

Abstract

top
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 f ₁ , f ₂ , . . . , f d of k-rainbow dominating functions on G with the property that ∑ i = 1 d | f i ( 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 d r k ( G ) . Note that d r 1 ( 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 d r k ( G ) . Many of the known bounds of d(G) are immediate consequences of our results.

How to cite

top

Seyyed Mahmoud Sheikholeslami, and Lutz Volkmann. "The k-rainbow domatic number of a graph." Discussiones Mathematicae Graph Theory 32.1 (2012): 129-140. <http://eudml.org/doc/271010>.

@article{SeyyedMahmoudSheikholeslami2012,
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 $\{f₁,f₂, ...,f_d\}$ of k-rainbow dominating functions on G with the property that $∑_\{i = 1\}^d |f_i(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 $d_\{rk\}(G)$. Note that $d_\{r1\}(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 $d_\{rk\}(G)$. Many of the known bounds of d(G) are immediate consequences of our results.},
author = {Seyyed Mahmoud Sheikholeslami, Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {k-rainbow dominating function; k-rainbow domination number; k-rainbow domatic number; -rainbow dominating function; -rainbow domination number; -rainbow domatic number},
language = {eng},
number = {1},
pages = {129-140},
title = {The k-rainbow domatic number of a graph},
url = {http://eudml.org/doc/271010},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Seyyed Mahmoud Sheikholeslami
AU - Lutz Volkmann
TI - The k-rainbow domatic number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 1
SP - 129
EP - 140
AB - 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 ${f₁,f₂, ...,f_d}$ of k-rainbow dominating functions on G with the property that $∑_{i = 1}^d |f_i(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 $d_{rk}(G)$. Note that $d_{r1}(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 $d_{rk}(G)$. Many of the known bounds of d(G) are immediate consequences of our results.
LA - eng
KW - k-rainbow dominating function; k-rainbow domination number; k-rainbow domatic number; -rainbow dominating function; -rainbow domination number; -rainbow domatic number
UR - http://eudml.org/doc/271010
ER -

References

top
  1. [1] C. Berge, Theory of Graphs and its Applications (Methuen, London, 1962). 
  2. [2] B. Brešar, M.A. Henning and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math. 12 (2008) 213-225. Zbl1163.05046
  3. [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. Zbl1126.05091
  4. [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. Zbl1226.05191
  5. [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. Zbl1183.05061
  6. [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. Zbl1081.05083
  7. [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. Zbl0384.05051
  8. [8] B. Hartnell and D.F. Rall, On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004) 389-402, doi: 10.7151/dmgt.1238. Zbl1063.05107
  9. [9] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc., New York, 1998). Zbl0890.05002
  10. [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. [11] D. B. West, Introduction to Graph Theory (Prentice-Hall, Inc, 2000). 
  12. [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. Zbl1209.05175

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.