赵衍才,尚华辉,A. Abdollahzadeh AHANGAR,N. Jafari RAD.符号混合控制问题的某些NP-完全性结果[J].数学研究及应用,2017,37(2):163~168
符号混合控制问题的某些NP-完全性结果
Some NP-Complete Results on Signed Mixed \\Domination Problem
投稿时间:2015-11-04  最后修改时间:2016-09-23
DOI:10.3770/j.issn:2095-2651.2017.02.004
中文关键词:  符号混合控制函数  符号混合控制数  NP-完全
英文关键词:signed mixed dominating function  signed mixed domination number  NP-completeness
基金项目:江苏省自然科学基金项目(Grant No.15B11009);河南省高等学校重点科研项目(15B110009).
作者单位
赵衍才 无锡城市职业技术学院基础课部, 江苏 无锡 214153 
尚华辉 永城职业学院基础课部, 河南 商丘 476600 
A. Abdollahzadeh AHANGAR Department of Mathematics, Babol Noshirvani University of Technology, Babol, Iran 
N. Jafari RAD Department of Mathematics, Shahrood University of Technology, Shahrood, Iran 
摘要点击次数: 531
全文下载次数: 620
中文摘要:
      设$G=(V,E)$是一个简单图,其点集合为$V$,边集合为$E$. $G$的一个符号混合控制函数是一个函数$f: V\cup E\rightarrow \{-1,1\}$,满足:对每个元素$x\in V\cup E$, $\sum_{y\in N_m(x)\cup\{x\}}f(y)\ge 1$.此处$N_m(x)$表示所有与$x$相邻或关联的点和边的集合. $f$的权$w(f)=\sum_{x\in V\cup E}f(x)$. 符号混合控制问题是指如何确定一个图的具有最小权的符号混合控制函数.本文研究符号混合控制问题的计算复杂性,我们证明了符号混合控制问题在二部图、弦图、甚至平面二部图上都是NP-完全的.
英文摘要:
      Let $G=(V,E)$ be a simple graph with vertex set $V$ and edge set $E$. A signed mixed dominating function of $G$ is a function $f$: $V\cup E\rightarrow \{-1,1\}$ such that $\sum_{y\in N_m(x)\cup\{x\}}f(y)\ge 1$ for every element $x\in V\cup E$, where $N_m(x)$ is the set of elements of $V\cup E$ adjacent or incident to $x$. The weight of $f$ is $w(f)=\sum_{x\in V\cup E}f(x)$. The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.
查看全文  查看/发表评论  下载PDF阅读器