The restrained rainbow bondage number of a graph

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

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.

Keywords


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

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.5556/j.tkjm.49.2018.2365

Sponsored by Tamkang University | ISSN 0049-2930 (Print), ISSN 2073-9826 (Online) | Powered by MathJax