Some NP-Complete Results on Signed Mixed \\Domination Problem

DOI：10.3770/j.issn:2095-2651.2017.02.004

 作者 单位 赵衍才 无锡城市职业技术学院基础课部, 江苏 无锡 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

设$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.