Signed mixed Roman domination numbers in graphs

被引:0
作者
H. Abdollahzadeh Ahangar
L. Asgharsharghi
S. M. Sheikholeslami
L. Volkmann
机构
[1] Babol University of Technology,Department of Basic Science
[2] Azarbaijan Shahid Madani University,Department of Mathematics
[3] RWTH Aachen University,Lehrstuhl II für Mathematik
来源
Journal of Combinatorial Optimization | 2016年 / 32卷
关键词
Signed Roman dominating function; Signed Roman domination number; Signed mixed Roman dominating function; Signed mixed Roman domination number; 05C69;
D O I
暂无
中图分类号
学科分类号
摘要
Let G=(V;E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G = (V;E)$$\end{document} be a simple graph with vertex set V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V$$\end{document} and edge set E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E$$\end{document}. A signed mixed Roman dominating function (SMRDF) of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is a function f:V∪E→{-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\cup E\rightarrow \{-1,1,2\}$$\end{document} satisfying the conditions that (i) ∑y∈Nm[x]f(y)≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{y\in N_m[x]}f(y)\ge 1$$\end{document} for each x∈V∪E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in V\cup E$$\end{document}, where Nm[x]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N_m[x]$$\end{document} is the set, called mixed closed neighborhood of x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x$$\end{document}, consists of x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x$$\end{document} and the elements of V∪E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V\cup E$$\end{document} adjacent or incident to x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x$$\end{document} (ii) every element x∈V∪E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x\in V\cup E$$\end{document} for which f(x)=-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(x) = -1$$\end{document} is adjacent or incident to at least one element y∈V∪E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y\in V\cup E$$\end{document} for which f(y)=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f(y) = 2$$\end{document}. The weight of a SMRDF f\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f$$\end{document} is ω(f)=∑x∈V∪Ef(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\omega (f)=\sum _{x\in V\cup E}f(x)$$\end{document}. The signed mixed Roman domination number γsR∗(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}^*(G)$$\end{document} of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is the minimum weight of a SMRDF of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document}. In this paper we initiate the study of the signed mixed Roman domination number and we present bounds for this parameter. In particular, we determine this parameter for some classes of graphs.
引用
收藏
页码:299 / 317
页数:18
相关论文
共 21 条
  • [1] Alavi Y(1977)Total matchings and total coverings of graphs J Graph Theory 1 135-140
  • [2] Behzad M(1977)On total matching numbers and total covering numbers of complementary graphs Discrete Math 19 229-233
  • [3] Lesniak-Foster LM(2013)On the mixed domination problem in graphs Theor Comput Sci 476 84-93
  • [4] Nordhaus EA(2007)A lower bound on the total signed domination numbers of graphs Sci China Ser A 50 1157-1162
  • [5] Erdös P(1999)On the algorithmic complexity of twelve covering and independence parameters of graphs Discrete Appl Math 91 155-175
  • [6] Meir A(2015)Signed mixed dominating functions in complete bipartite graphs Int J Comput Math 92 712-721
  • [7] Lana JK(2015)The signed Roman domatic number of a digraph Electron J Graph Theory Appl 3 85-93
  • [8] Chang GJ(2012)The signed Roman domatic number of a graph Ann Math Inform 40 105-112
  • [9] Lv XZ(2002)On signed edge domination numbers of trees Math Bohemica 127 49-55
  • [10] Manlove DF(2011)The algorithmic complexity of mixed domination in graphs Theor Comput Sci 412 2387-2392