The k-Rainbow Domination and Domatic Numbers of Digraphs
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
For a positive integer $k$, a {\em$k$-rainbow dominating function} of a digraph $D$ is a function $f$from the vertex set $V(D)$ to the set of all subsets of the set$\{1,2,\ldots,k\}$ such that for any vertex $v\in V(D)$ with$f(v)=\emptyset$ the condition $\bigcup_{u\inN^-(v)}f(u)=\{1,2,\ldots,k\}$ is fulfilled, where $N^-(v)$ is theset of in-neighbors of $v$. A set $\{f_1,f_2,\ldots,f_d\}$ of$k$-rainbow dominating functions on $D$ with the property that$\sum_{i=1}^d|f_i(v)|\le k$ for each $v\in V(D)$, is called a {\em$k$-rainbow dominating family} (of functions) on $D$. The maximumnumber of functions in a $k$-rainbow dominating family on $D$ is the{\em $k$-rainbow domatic number} of $D$, denoted by $d_{rk}(D)$. Inthis paper we initiate the study of the $k$-rainbow domatic numberin digraphs, and we present some bounds for $d_{rk}(D)$.
Abstract
For a positive integer $k$, a {\em$k$-rainbow dominating function} of a digraph $D$ is a function $f$from the vertex set $V(D)$ to the set of all subsets of the set$\{1,2,\ldots,k\}$ such that for any vertex $v\in V(D)$ with$f(v)=\emptyset$ the condition $\bigcup_{u\inN^-(v)}f(u)=\{1,2,\ldots,k\}$ is fulfilled, where $N^-(v)$ is theset of in-neighbors of $v$. A set $\{f_1,f_2,\ldots,f_d\}$ of$k$-rainbow dominating functions on $D$ with the property that$\sum_{i=1}^d|f_i(v)|\le k$ for each $v\in V(D)$, is called a {\em$k$-rainbow dominating family} (of functions) on $D$. The maximumnumber of functions in a $k$-rainbow dominating family on $D$ is the{\em $k$-rainbow domatic number} of $D$, denoted by $d_{rk}(D)$. Inthis paper we initiate the study of the $k$-rainbow domatic numberin digraphs, and we present some bounds for $d_{rk}(D)$.
참고문헌 (20)
- J. Amjadi, "The rainbow domination number of a digraph", Kragujevac J. Math., 37, pp.257~268 (2013)
- J. Amjadi, "The k-rainbow bondage number of a digraph", Discuss. Math. Graph Theory, 35, pp.261~270 (2015)
- B. Bresar, "Rainbow domination in graphs", Taiwanese J. Math., 12, pp.213~225 (2008)
- B. Bresar, "On the 2-rainbow domination in graphs", Discrete Appl. Math., 155, pp.2394~2400 (2007)
- G. J. Chang, "Rainbow domination on trees", Discrete Appl. Math., 158, pp.8~12 (2010)
- G. Chartrand, "On the out-domination and in-domination numbers of a digraph", Discrete Math., 197, pp.179~183 (1999)
- T. Chunling, "2-rainbow domination of generalized Petersen graphs P(n; 2)", Discrete Appl. Math., 157, pp.1932~1937 (2009)
- N. Dehgardi, "The rainbow domination subdi-vision numbers of graphs", Mat. Vesnik Mat. Vesnik, 67, pp.102~114 (2015)
- M. Falahat, "New bounds on the rainbow domination subdivision number", Filomat, 28, pp.615~622 (2014)
- S. Fujita, "k-Rainbow domatic numbers", Discrete. Appl. Math., 160, pp.1104~1113 (2012)
- J. Ghoshal, "Topics on domination in directed graphs", 401~437
- T. W. Haynes, "Fundamentals of Domination in Graphs" (1998), Marcel Dekker, Inc.
- T. W. Haynes, "Domination in graphs, Advanced Topics" (1998), Marcel Dekker, Inc.
- C. Lee, "On the domination number of a digraph", PhD thesis, Department of Mathe-matics, pp.1994
- C. Lee, "Domination in digraphs", J. Korean Math. Soc., 35, pp.843~853 (1998)
- D. Meierling, "Nordhaus-Gaddum bounds on the k-rainbow domatic number of a graph", Applied Math. Letters, 24, pp.1758~1761 (2011)
- S. M. Sheikholeslami, "The k-rainbow domatic number of a graph", Discuss. Math. Graph Theory, 32, pp.129~140 (2012)
- G. Xu, "2-rainbow domination of generalized Petersen graphs P(n; 3)", Discrete Appl. Math., 157, pp.2570~2573 (2009)
- X. D. Zhang, "On domination number of Cartesian product of directed cycles", Inform. Process. Lett., 111, pp.36~39 (2010)
- B. Zelinka, "Semidomatic numbers of directed graphs", Math. Slovaca, 34, pp.371~374 (1984)