The k-Rainbow Bondage Number of a Digraph

Jafar Amjadi; Negar Mohammadi; Seyed Mahmoud Sheikholeslami; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 261-270
  • ISSN: 2083-5892

Abstract

top
Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF of D. The k-rainbow bondage number brk(D) of a digraph D with maximum in-degree at least two, is the minimum cardinality of all sets A′ ⊆ A for which γrk(D−A′) > γrk(D). In this paper, we establish some bounds for the k-rainbow bondage number and determine the k-rainbow bondage number of several classes of digraphs.

How to cite

top

Jafar Amjadi, et al. "The k-Rainbow Bondage Number of a Digraph." Discussiones Mathematicae Graph Theory 35.2 (2015): 261-270. <http://eudml.org/doc/271087>.

@article{JafarAmjadi2015,
abstract = {Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set \{1, 2, . . . , k\} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = \{1, 2, . . . , k\} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF of D. The k-rainbow bondage number brk(D) of a digraph D with maximum in-degree at least two, is the minimum cardinality of all sets A′ ⊆ A for which γrk(D−A′) > γrk(D). In this paper, we establish some bounds for the k-rainbow bondage number and determine the k-rainbow bondage number of several classes of digraphs.},
author = {Jafar Amjadi, Negar Mohammadi, Seyed Mahmoud Sheikholeslami, Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {k-rainbow dominating function; k-rainbow domination number; k-rainbow bondage number; digraph; -rainbow dominating function; -rainbow domination number; -rainbow bondage number},
language = {eng},
number = {2},
pages = {261-270},
title = {The k-Rainbow Bondage Number of a Digraph},
url = {http://eudml.org/doc/271087},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Jafar Amjadi
AU - Negar Mohammadi
AU - Seyed Mahmoud Sheikholeslami
AU - Lutz Volkmann
TI - The k-Rainbow Bondage Number of a Digraph
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 261
EP - 270
AB - Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF of D. The k-rainbow bondage number brk(D) of a digraph D with maximum in-degree at least two, is the minimum cardinality of all sets A′ ⊆ A for which γrk(D−A′) > γrk(D). In this paper, we establish some bounds for the k-rainbow bondage number and determine the k-rainbow bondage number of several classes of digraphs.
LA - eng
KW - k-rainbow dominating function; k-rainbow domination number; k-rainbow bondage number; digraph; -rainbow dominating function; -rainbow domination number; -rainbow bondage number
UR - http://eudml.org/doc/271087
ER -

References

top
  1. [1] J. Amjadi, A. Bahremandpour, S.M. Sheikholeslami and L. Volkmann, The rainbow domination number of a digraph, Kragujevac J. Math. 37 (2013) 257-268. Zbl1299.05249
  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[WoS][Crossref] 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[Crossref] Zbl1226.05191
  5. [5] Ch. Tong, X. Lin, Y. Yang and M.Luo, 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[Crossref] Zbl1183.05061
  6. [6] N. Dehgardi, S.M. Sheikholeslami and L. Volkmann, The k-rainbow bondage number of a graph, Discrete Appl. Math. 174 (2014) 133-139. doi:10.1016/j.dam.2014.05.006[Crossref][WoS] Zbl1297.05080
  7. [7] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, The bondage number of a graph, Discrete Math. 86 (1990) 47-57. doi:10.1016/0012-365X(90)90348-L[Crossref] 
  8. [8] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998). Zbl0890.05002
  9. [9] 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) 1758-1761. doi:10.1016/j.aml.2011.04.046[Crossref][WoS] Zbl1222.05200
  10. [10] S.M. Sheikholeslami and L. Volkmann, The k-rainbow domatic number of a graph, Discuss. Math. Graph Theory 32 (2012) 129-140. doi:10.7151/dmgt.1591[Crossref] Zbl1255.05139
  11. [11] D.B. West, Introduction to Graph Theory (Prentice-Hall, Inc., 2000). 
  12. [12] Y. Wu and N. Jafari Rad, Bounds on the 2-rainbow domination number of graphs, Graphs Combin. 29 (2013) 1125-1133. doi:10.1007/s00373-012-1158-y[Crossref] Zbl1268.05154
  13. [13] G. Xu, 2-rainbow domination in generalized Petersen graphs P(n, 3), Discrete Appl. Math. 157 (2009) 2570-2573. doi:10.1016/j.dam.2009.03.016 [Crossref] 

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.