Some NPComplete Results on Signed Mixed \\Domination Problem 
Received:November 04, 2015 Revised:September 23, 2016 
Key Word:
signed mixed dominating function signed mixed domination number NPcompleteness

Fund ProjectL: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: 325 
Download times: 491 
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 minimumweight 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 NPcomplete for bipartite graphs, chordal graphs, even for planar bipartite graphs. 
Citation: 
DOI:10.3770/j.issn:20952651.2017.02.004 
View Full Text View/Add Comment Download reader 


