Operations Research Transactions ›› 2012, Vol. 16 ›› Issue (1): 41-48.

• Original Articles • Previous Articles     Next Articles

Positive Influencing Number of Partitioned Graphs

ZHAO Weiliang1, ZHAO Yancai2   

  1. 1. Zhejiang Industry Polytechnic College, Zhejiang Shaoxing 312000,  China; 2. Department of Mathematics and Physics, Bengbu College, Anhui Bengbu 233030, China
  • Received:2011-03-21 Revised:2011-07-18 Online:2012-03-15 Published:2012-03-15
  • Contact: Wei-Liang ZHAO E-mail:zwl@shu.edu.cn
  • Supported by:

    This research was supported by the foundation from Department of Education of Zhejiang Province (No.Y201018696), the Nature Science Foundation of Anhui Provincial Education Department (No. KJ2011B090).

Abstract: In this paper, a concept is introduced in order to model a class of problems in social networks. A social network consisting of positive and negative influential individuals is represented as a partitioned graph G=(V,E) with vertex set partition V=V+\cup V-. A subset D\subseteq V- is called a positive influencing set if every vertex  of  G has  in D\cup V+ at least half of its neighbors. The positive influencing number of G is the minimum cardinality of a positive influencing set. In the present paper, we show some sharp lower bounds for this parameter, and prove that this problem is NP-complete for partitioned bipartite graphs and partitioned chordal graphs, respectively.

Key words: total domination, signed total domination, positive influencing number, social networks