| Some NP-Complete Results on Signed Mixed \\Domination Problem |
| Received:November 04, 2015 Revised:September 23, 2016 |
| Key Words:
signed mixed dominating function signed mixed domination number NP-completeness
|
| Fund Project:Supported by the Natural Science Foundation of Jiangsu Province (Grant No.BK20151117) and the Key Scientific Research Foundation of Higher Education Institutions of Henan Province (Grant No.15B110009). |
| Author Name | Affiliation | | Yancai ZHAO | Department of Basic Science, Wuxi City College of Vocational Technology, Jiangsu 214153, P. R. China | | Huahui SHANG | Department of Basic Science, Yongcheng Vocational College, Henan 476600, P. R. China | | 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 |
|
| Hits: 3206 |
| Download times: 2309 |
| 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. |
| Citation: |
| DOI:10.3770/j.issn:2095-2651.2017.02.004 |
| View Full Text View/Add Comment |
|
|
|
