符号混合控制问题的某些NP-完全性结果

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

中文关键词:  符号混合控制函数  符号混合控制数  NP-完全

英文关键词:signed mixed dominating function  signed mixed domination number  NP-completeness

中文摘要:

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