The restrained rainbow bondage number of a graph

Authors

  • Jafar Amjadi
  • Rana Khoeilar
  • N. Dehgardi
  • Lutz Volkmann
  • S.M. Sheikholeslami

DOI:

https://doi.org/10.5556/j.tkjm.49.2018.2365

Keywords:

$k$-rainbow domination number, restrained $k$-rainbow domination number, restrained $k$-rainbow bondage number

Abstract

A restrained $k$-rainbow dominating function (R$k$RDF) 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,\ldots,k\}$ such that for any vertex $v \in V (G)$ with $f(v) = \emptyset$ the conditions $\bigcup_{u \in N(v)} f(u)=\{1,2,\ldots,k\}$ and $|N(v)\cap \{u\in V\mid f(u)=\emptyset\}|\ge 1$ are fulfilled, where $N(v)$ is the open neighborhood of $v$. The weight of a restrained $k$-rainbow dominating function is the value $w(f)=\sum_{v\in V}|f (v)|$. The minimum weight of a restrained $k$-rainbow dominating function of $G$ is called the restrained $k$-rainbow domination number of $G$, denoted by $\gamma_{rrk}(G)$. The restrained $k$-rainbow bondage number $b_{rrk}(G)$ of a graph $G$ with maximum degree at least two is the minimum cardinality of all sets $F \subseteq E(G)$ for which $\gamma_{rrk}(G-F) > \gamma_{rrk}(G)$. In this paper, we initiate the study of the restrained $k$-rainbow bondage number in graphs and we present some sharp bounds for $b_{rr2}(G)$. In addition, we determine the restrained 2-rainbow bondage number of some classes of graphs.

Author Biographies

Jafar Amjadi

Department of Mathematics, Azarbaijan ShahidMadani University, Tabriz, I.R. Iran.

Rana Khoeilar

Department of Mathematics, Azarbaijan ShahidMadani University, Tabriz, I.R. Iran.

N. Dehgardi

Department of Mathematics and Computer Science, Sirjan University of Technology, Sirjan, I.R. Iran.

Lutz Volkmann

Lehrstuhl II fürM athematik, RWTH Aachen University, 52056 Aachen, Germany.

S.M. Sheikholeslami

Department ofMathematics, Azarbaijan ShahidMadani University, Tabriz, I.R. Iran.

References

H. A. Ahangar, J. Amjadi, V. Samodivkin, S. M. Sheikholeslami and L. Volkmann, On the rainbow restrained domination number, Ars Combin., 125 (2016), 209--224.

J. Amjadi, L. Asgharshrgi, N. Dehgardi, M. Furuya, S. M. Sheikholeslami and L. Volkmann,The $k$-rainbow reinforcement numbers in graphs, Discrete Appl. Math., 217 (2017), 394--404.

J. Amjadi, N. Dehgardi, M. Furuya and S. M. Sheikholeslami, A sufficient condition for large rainbow domination number,International Journal of Computer Mathematics: Computer Systems Theory, 2(2017), 53--65.

J. Amjadi and A. Parnian, On the $2$-rainbow bondage number of planar graphs, Ars Combin., 126(2016), 395--405.

J. Amjadi, S. M. Sheikholeslami and L. Volkmann, Rainbow restrained domination numbers in graphs, Ars Combin., 124(2016), 3--19.

L. Asgharsharghi, S. M. Sheikholeslami and L. Volkmann, A note on the $2$-rainbow bondage numbers in graphs, Asian-European J. Math., 9(2016), 1650013 (7 pages)

B. Brevsar, M.A. Henning, and D.F. Rall, Rainbow domination in graphs, Taiwanese J. Math., 12(2008), 213--225.

B. Bre$checkrm s$ar, and T.K. $checkrm S $umenjak, On the 2-rainbow domination in graphs, Discrete Appl. Math., 155(2007), 2394--2400.

G. J. Chang, J. Wu and X. Zhu, Rainbow domination on trees, Discrete Appl. Math., 158(2010), 8--12.

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.

N. Dehgardi, S. M. Sheikholeslami and L. Volkmann, The k-rainbow bondage number of a graph, Discrete Appl. Math.,174(2014), 133--139.

G. S. Domke, J. H. Hattingh, S. T. Hedetniemi and L. R. Markus, Restrained domination in trees, Discrete Math., 211(2000), 1--9.

G. S. Domke, J. H. Hattingh, M. A. Henning and L. R. Markus, Restrained domination in graphs with minimum degree two, J. Combin. Math. Combin. Comput., 35(2000), 239--254.

G. S. Domke, J. H. Hattingh, S. T. Hedetniemi, R. C. Laskar, and L. R. Markus,Restrained domination in graphs, Discrete Math., 203(1999), 61--69.

J.H. Hattingh and A.R. Plummer, Restrained bondage in graphs, Discrete Math., 308(2008), 5446--5453.

B. Hartnell and D. F. Rall, On dominating the Cartesian product of a graph and $K_2$, Discuss. Math. Graph Theory, 24(2004),389--402.

T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs}, Marcel Dekker, Inc.New York, 1998.

R. Kala and T. R. Nirmala Vasantha, Restrained bondage number of a graph, J. Discrete Math. Sci. Cryptogr., 12(2009),373--380.

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.

Z. Shao, M. Liang, C. Yin, X. Xu, P. Pavliv c and J.$check{{rm Z}}$erovnik, On rainbow domination numbers of graphs,Information Sciences, 254(2014), 225--234.

S. M. Sheikholeslami and L. Volkmann, The $k$-rainbow domatic number of a graph,Discuss. Math. Graph Theory, 32 (2012), 129--140.

D. B. West, Introduction to Graph Theory,Prentice-Hall, Inc, 2000.

Y. Wu and N. Jafari Rad, Bounds on the $2$-rainbow domination number of graphs, Graphs Combin., 29 (2013), 1125--1133.

G. Xu, $2$-rainbow domination of generalized Petersen graphs $P(n,3)$, Discrete Appl. Math.,157(2009), 2570--2573.

Downloads

Published

2018-06-30

How to Cite

Amjadi, J., Khoeilar, R., Dehgardi, N., Volkmann, L., & Sheikholeslami, S. (2018). The restrained rainbow bondage number of a graph. Tamkang Journal of Mathematics, 49(2), 115-127. https://doi.org/10.5556/j.tkjm.49.2018.2365

Issue

Section

Papers