Some NP-Complete Results on Signed Mixed \\Domination Problem
Received:November 04, 2015  Revised:September 23, 2016
Key Word: signed mixed dominating function   signed mixed domination number   NP-completeness  
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 NameAffiliation
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: 461
Download times: 583
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  Download reader