English

运筹学学报 ›› 2012, Vol. 16 ›› Issue (1): 41-48.

• 运筹学 • 上一篇    下一篇

划分图上的正影响数

赵伟良1, 赵衍才2   

  1. 1. 浙江工业职业技术学院, 浙江绍兴, 31200; 2. 蚌埠学院数学与物理系，安徽蚌埠, 33030
  • 收稿日期:2011-03-21 修回日期:2011-07-18 出版日期:2012-03-15 发布日期:2012-03-15
  • 通讯作者: 赵伟良 E-mail:zwl@shu.edu.cn

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).

PDF

1184

被引次数

2

摘要： 一个社会网络中通常包括具有正面影响和负面影响的两类人员，为了研究这个社会网络中人们之间相互影响的某些规律，引入了一个新的概念. 用划分图G=(V,E),V=V+ \cup V-表示这样的一个社会网络，其中V+和V- 分别表示正面人员的集合和负面人员的集合. 图G的一个点子集D\subseteq V-被称为G的一个正影响集，若G的每个点的至少一半的邻点在D\cup V+中. G的所有正影响集的最小基数称为G的正影响数. 给出G的正影响数的几个下界并证明了这些界是紧的. 此外，还证明了求正影响数问题在二部图和弦图上都是NP-完全的.

关键词: 全控制, 符号全控制, 正影响数, 社会网络

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