Positive influence domination in graphs
type: Item
instance of: scholarly article
title: Positive influence domination in graphs
zbMATH Open document ID: 1505.05108
author: Nian Wang
author: Yan Zhang
author: Jingting Xiao
author: Haichao Wang
author: Yu-Qin Sun
published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series
publication date: 2022-10-04T00:00:00Z
review text: The concept of positive influence dominating set has interesting applications in social network analysis. A subset \(D\) of \(V\) is called a positive influence dominating set (PIDS) of a graph \(G\) if every vertex \(v\) has at least half of its neighbors in \(D.\) Since an individual is inclined to hold positive opinion if more of his friends have a positive opinion and hence, a PIDS can produce a globally positive influence on the entire social network. Sharp lower bounds for the positive influence domination \(\gamma_{PT}(G)\) are presented. From the algorithmic perspective, it is proved that the decision version of the positive influence domination problem is NP-complete even when restricted to bipartite graphs and split graphs. Furthermore, the problem remains APX-complete on graphs with a maximum degree of three.
reviewed by: S. Arumugam
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 91D30
zbMATH DE Number: 7596030
zbMATH Keywords: positive influence dominating set
zbMATH Keywords: positive influence domination number
zbMATH Keywords: bounds
zbMATH Keywords: NP-complete
zbMATH Keywords: APX-complete
MaRDI profile type: Publication
full work available at URL: s40840-022-01343-8
OpenAlex ID: W4286717547
cites work: Q4258216
cites work: Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
cites work: Q4942157
cites work: On the approximability of positive influence dominating set in social networks
cites work: Q4198056
cites work: Q4368729
cites work: Q4368728
cites work: Minus domination number in \(k\)-partite graphs.
cites work: Q3688433
cites work: Optimization, approximation, and complexity classes
cites work: Positive Influence Dominating Set in Online Social Networks
cites work: On positive influence dominating sets in social networks
DOI: 10.1007/S40840-022-01343-8
description: scientific article; zbMATH DE number 7596030