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： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x...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： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x） is the set of elements of V U E adjacent or incident to x. The weight of f isw（f）∑x∈VUEf（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.展开更多
基金Supported by the Natural Science Foundation of Jiangsu Province(Grant No.BK20151117)the Key Scientific Research Foundation of Higher Education Institutions of Henan Province(Grant No.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： VUE→{-1,1}such that ∑y∈Nm（x）U{x}f（y） ≥1 for every element x ∈ V U E, where Nm （x） is the set of elements of V U E adjacent or incident to x. The weight of f isw（f）∑x∈VUEf（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.
