| 符号混合控制问题的某些NP-完全性结果 |
| |
| 引用本文： | 赵衍才,尚华辉,A. Abdollahzadeh AHANGAR,N. Jafari RAD.符号混合控制问题的某些NP-完全性结果[J].数学研究及应用,2017,37(2):163-168. |
| |
| 作者姓名： | 赵衍才 尚华辉 A. Abdollahzadeh AHANGAR N. Jafari RAD |
| |
| 作者单位： | 无锡城市职业技术学院基础课部, 江苏 无锡 214153,永城职业学院基础课部, 河南 商丘 476600,Department of Mathematics, Babol Noshirvani University of Technology, Babol, Iran,Department of Mathematics, Shahrood University of Technology, Shahrood, Iran |
| |
| 基金项目： | 江苏省自然科学基金项目(Grant No.15B11009)；河南省高等学校重点科研项目(15B110009). |
| |
| 摘 要： | 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∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪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.
|
| 关 键 词： | 符号混合控制函数 符号混合控制数 NP-完全 |
| 收稿时间： | 2015/11/4 0:00:00 |
| 修稿时间： | 2016/9/23 0:00:00 |
Some NP-Complete Results on Signed Mixed \\Domination Problem |
| |
| Yancai ZHAO,Huahui SHANG,A. Abdollahzadeh AHANGAR and N. Jafari RAD.Some NP-Complete Results on Signed Mixed \\Domination Problem[J].Journal of Mathematical Research with Applications,2017,37(2):163-168. |
| |
| Authors: | Yancai ZHAO Huahui SHANG A Abdollahzadeh AHANGAR and N Jafari RAD |
| |
| Institution: | Department of Basic Science, Wuxi City College of Vocational Technology, Jiangsu 214153, P. R. China,Department of Basic Science, Yongcheng Vocational College, Henan 476600, P. R. China,Department of Mathematics, Babol Noshirvani University of Technology, Babol, Iran and Department of Mathematics, Shahrood University of Technology, Shahrood, Iran |
| |
| Abstract: | 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. |
| |
| Keywords: | signed mixed dominating function signed mixed domination number NP-completeness |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
| 点击此处可从《数学研究及应用》下载免费的PDF全文 |
|
