Signed Roman k-domination in Digraphs

被引:0
作者
Lutz Volkmann
机构
[1] RWTH Aachen University,Lehrstuhl II für Mathematik
来源
Graphs and Combinatorics | 2016年 / 32卷
关键词
Digraph; Signed Roman ; -dominating function; Signed Roman ; -domination number; 05C20; 05C69;
D O I
暂无
中图分类号
学科分类号
摘要
Let k≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 1$$\end{document} be an integer, and let D be a finite and simple digraph with vertex set V(D). A signed Roman k-dominating function (SRkDF) on a digraph D is a function f:V(D)→{-1,1,2}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f:V(D)\rightarrow \{-1,1,2\}$$\end{document} satisfying the conditions that (1) ∑x∈N-[v]f(x)≥k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{x\in N^-[v]}f(x)\ge k$$\end{document} for each v∈V(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v\in V(D)$$\end{document}, where N-[v]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N^-[v]$$\end{document} consists of v and all vertices of D from which arcs go into v, and (2) every vertex u for which f(u)=-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(u)=-1$$\end{document} has an inner neighbor v for which f(v)=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(v)=2$$\end{document}. The weight of an SRkDF f is w(f)=∑v∈V(D)f(v)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w(f)=\sum _{v\in V(D)}f(v)$$\end{document}. The signed Roman k-domination number γsRk(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _{sR}^k(D)$$\end{document} of D is the minimum weight of an SRkDF on D. In this paper we initiate the study of the signed Roman k-domination number of digraphs, and we present different bounds on γsRk(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _{sR}^k(D)$$\end{document}. In addition, we determine the signed Roman k-domination number of some classes of digraphs. Some of our results are extensions of well-known properties of the signed Roman domination number γsR(D)=γsR1(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _{sR}(D)=\gamma _{sR}^1(D)$$\end{document} and the signed Roman k-domination number γsRk(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma _{sR}^k(G)$$\end{document} of graphs G.
引用
收藏
页码:1217 / 1227
页数:10
相关论文
共 16 条
[1]  
Ahangar HA(2014)Signed Roman domination in graphs J. Comb. Optim. 27 241-255
[2]  
Henning MA(2010)The signed Cent. Eur. J. Math. 8 1048-1057
[3]  
Löwenstein C(2009)-domination number of directed graphs Discret. Math. 309 2567-2570
[4]  
Zhao Y(2015)Lower bounds on the signed domination numbers of directed graphs J. Comb. Optim. 30 456-467
[5]  
Samodivkin V(2011)Signed Roman domination in digraphs Math. Graph Theory 31 415-427
[6]  
Atapour M(2005)Signed domination and signed domatic numbers of digraphs Discuss Czechoslovak Math. J. 55 479-482
[7]  
Hajypory R(undefined)Signed domination numbers of directed graphs undefined undefined undefined-undefined
[8]  
Sheikholeslami SM(undefined)undefined undefined undefined undefined-undefined
[9]  
Volkmann L(undefined)undefined undefined undefined undefined-undefined
[10]  
Karami H(undefined)undefined undefined undefined undefined-undefined